非均衡NIM

张三和李四因为每天都玩取石子游戏而感到厌倦，因此他们给普通的三堆取石子游戏增加了一条规则：任意一轮中三堆石子的数量必须都各不相同，相应地，当三堆石子的数量分别为$0,1,2$（或其任何排列）时游戏结束。

在此新规则下$(2,4,5)$将成为一必败的局面，一种可能的局面演化如下： $$(2,4,5)\mapsto(2,4,3)\mapsto(0,4,3)\mapsto(0,2,3)\mapsto(0,2,1).$$ 给定$N$，考虑所有满足$0 < a < b < c < N$的必败局面$(a,b,c)$，记这些局面的$a+b+c$之和为$F(N)$。

可以验证，$N=8$时满足上述条件的局面共有$(1,3,5), (1,4,6), (2,3,6), (2,4,5)$四组，因此$F(8)=42$。同样也可以验证$F(128)=496062$。

求$F(10^{18})的最后九位数字$。

本题难度:

解答

根据官方论坛的提示，本题可在《On Numbers and Games》（J.H.Conway）的第十三章找到。

当且仅当$(a+1,b+1,c+1)$是经典NIM中的必胜局时$(a,b,c)$才是此变体中的必胜局。最终结果是$216737278$。

N=10**18+1

def f(n):
    if n <= 1:
        return 0
    x=1
    while 2*x <= n:
        x*=2
    return x*x*(x-1)//4+(n-x)*x*(x-1)//2+x*x*(n-x)+f(n-x)

res=0
b=1
while 2*b <= N:
    s=b*(b-1)//2
    res+=f(b)+(2*b-3)*s+(b*(b-1)*(2*b-1)//2-s)//2
    b*=2
s=(N-b)*(N-b-1)//2
res+=f(N-b)+(2*b-3)*s+((N-b)*(N-b-1)*(2*N-2*b-1)//2-s)//2-(N//2-1)*(2*(N//2)-1)
print res%1000000000