本题与第301题，第306题，第310题，第325题的背景都相同，即NIM游戏的变体，本题也是第二道官网难度标记为100\%的问题，以下仅作扼要提示：
用$x_1,\ldots,x_{101}$来表示这些硬币的位置。若银币在最左侧，则显然先手直接胜，否则若$x_k$是硬币，则再记$x_0=2-k$。
令$y_i=x_{2i+i}-x_{2i}-1$，则本游戏就转换为了每堆数量为$y_i$的取石头游戏（即NIM），从而只有在全部$y_i$的异或值为$0$时后手胜。
注意后手总是可以保持异或值不变，这是因为若某个$y_i$增加，说明$x_{2i}$被左移，则只需将$x_{2i+1}$移动同样的距离。
若其减少但未减至0，则后手可以将其减少至0来保持异或值。若其减少至0，则后手可以将另一项$y_{i'}$减少至0，同样可以保持异或值。
而$x_0$的选取刻画了胜负条件，例如$x_2$是银币时任意一方都不会将$y_0$减少到0，否则下一轮对手直接获胜。
用动态规划递推汇总$y_i$之和为t，且异或值为$0$的局面数，最终结果是$65579304332$。
注：因需要用到math.comb方法，以下代码为Python 3。
import math
def f(k,shift=0):
r=0
m=n-c
d=[0]*(m+1)
d[0]=1
for t,x in enumerate(d):
if x>0:
r+=x*math.comb(m-(t+shift)+p,p)
for i in range(2*(t==0),min([m-2*t,p+k])+1,2):
d[2*t+i]+=x*b[k][i]
return r
n=10**6
c=100
p=50
b=[[math.comb(p+i,j) for j in range(p+i+1)] for i in range(2)]
print(((c+1)*math.comb(n,c+1)+(c-1)*(f(0)-f(1))-f(1,1))%1000036000099)
|
