跳跃游戏

将0到k的二进制表示中1的总数记作$s_k$。

例如0到5的二进制表示分别是0、1、10、11、100、101，其中共有7个1，因此$s_5=7$。

从$k=0$开始$s_k$的前几项依次是$0, 1, 2, 4, 5, 7, 9, 12, \ldots$。

两名玩家正在玩这样一个游戏：游戏开始前选定一个数n，并将计数器c置0。两名玩家依次从1至n中选择一个数（包括1和n），然后把这个数加到计数器c中，要求所得的结果必须在集合S中。若不存在可行的操作，则当前玩家输掉游戏。

例如：取n = 5。

玩家1选择4，因此c变为$0+4=4$。

玩家2选择5，因此c变为$4+5=9$。

玩家1选择3，因此c变为$9+3=12$。

以此类推。

记$M(n)$为先手玩家在保证必胜的前提下，在第一轮所能选择的最大的数。如果不存在这样的数，则令$M(n)=0$。

可以验证$M(2)=2, M(7)=1, M(20)=4$以及$\sum_{n=1}^{20}M^3(n)=8150$。

求$\sum_{n=1}^{1000}M^3(n)$。

本题难度:

解答

$s_k$的生成公式可以参考OEIS A000788。

经过一些尝试可以发现$M(n)$似乎和步数有关，当步数充分大时，$M(n)$是关于步数的分段常值函数，可以以此设置循环上界。

以下代码改编自官方论坛，最终结果是$61029882288$。

def compute(n):
  M[0][n]=M[1][n]=n
  k,step=1,n+1
  for s in range(1,step+1):
      for m in range(1,s+1):
          for v in range(n+1):
              value=M[k][((m-1)<<10)+v]+s-m+1
              if value>=step:
                  value=0
              M[k][(m<<10)+v]=M[1-k][((m-1)<<10)+value]
      value,v=M[k][(s<<10)],1
      while v<=n and M[k][(s<<10)+v]==value:
          v+=1
      if v>n: 
          return value
      k=1-k
  return M[1-k][(step<<10)]

M=[[0]*(1<<20),[0]*(1<<20)]
print sum(compute(i)**3 for i in range(0,1000+1))