取石头二
|
两名玩家正在用两堆石子进行取石头游戏，用$(a,b)$表示当前游戏的状态（即两堆石头的数量）。
每轮中当前玩家可以从较大的堆中取走一定数量的石头，所取走的石头数量必须是较小的堆中石头数量的正整数倍。
例如状态为$(6,14)$时玩家可以从第二堆中取走6个或12个石头。
先取完某一堆中所有石头的玩家获胜。
所谓必胜态是指当前玩家必胜的状态。例如$(1,5), (2,6), (3,12)$都是必胜态，因为当前玩家可以立即取走第二个堆中的所有石头。
所谓必败态是指无论当前玩家如何操作都必败的状态。例如$(2,3), (3,4)$都是必败态。
记$S(N)$为所有满足$0 < x < y < N$的必败态$(x,y)$所对应的$x+y$之和，可以验证$S(10)=211, S(10^4)=230312207313$。
求$S(10^{16}) \bmod 7^{10}$。
|
本题难度:
|
解答
|
本题的机制比较复杂，通过模拟可以发现对每个x，都存在这样一个$f(x)$，使得当且仅当$x < y < f(x)$时$(x,y)$是必败态。
当$x\to\infty$时可以观察到$f(x)/x\to (1+\sqrt5)/2$。接下来利用这一规律求和，记$\phi=(1+\sqrt5)/2$ (注意$\phi$是黄金分割)，则有
$$S(N)=\sum_{y=2}^{N-1}\sum_{x=\lceil y/\phi \rceil}^{y-1}(x+y)=\frac{1}{2}\sum_{y=2}^{N-1}(\lceil y/\phi \rceil+3y-1)(y-\lceil y/\phi \rceil),$$
注意到
$$1+\frac{1}{\phi}=1+\frac{2}{1+\sqrt5}=1+\frac{\sqrt 5-1}{2}=\frac{1+\sqrt 5}{2}=\phi,$$
因此上式可以进一步写作
$$S(N)=\frac{1}{2}\sum_{y=2}^{N-1}(\lceil y\phi \rceil+2y-1)(2y-\lceil y\phi \rceil)=\sum_{y=2}^{N}(2y^2+y-\frac{\lceil y\phi \rceil^2+\lceil y\phi \rceil}{2}),$$
接下来用求和公式直接计算即得结果$54672965$。
import math
target=10**16
m=7**10
phi=(1+math.sqrt(5))/2
def cal(n):
if n==1:return 1,1
k=int(n/phi)
a,b=cal(k)
t=((n*(n+1)/2)*k+n*(n+1)*(2*n+1)/6-a)%m
f=(n*k*(k+1)/2-(n*n*n-n)/6+t-b)%m
return f,t
print ((4*target-1)*target*(target+1)/6-cal(target)[0])%m
|
| |
