Project Euler 391

题目

Hopping Game

Let \(s_k\) be the number of \(1\)’s when writing the numbers from \(0\) to \(k\) in binary.

For example, writing \(0\) to \(5\) in binary, we have \(0, 1, 10, 11, 100, 101\). There are seven \(1\)’s, so \(s_5 = 7\).

The sequence \(S = \{s_k : k \ge 0\}\) starts \(\{0, 1, 2, 4, 5, 7, 9, 12, \dots\}\).

A game is played by two players. Before the game starts, a number \(n\) is chosen. A counter \(c\) starts at \(0\). At each turn, the player chooses a number from \(1\) to \(n\) (inclusive) and increases \(c\) by that number. The resulting value of \(c\) must be a member of \(S\). If there are no more valid moves, then the player loses.

For example, with \(n = 5\) and starting with \(c = 0\):

Player \(1\) chooses \(4\), so \(c\) becomes \(0 + 4 = 4\).

Player \(2\) chooses \(5\), so \(c\) becomes \(4 + 5 = 9\).

Player \(1\) chooses \(3\), so \(c\) becomes \(9 + 3 = 12\).

etc. Note that \(c\) must always belong to \(S\), and each player can increase \(c\) by at most \(n\).

Let \(M(n)\) be the highest number that the first player could choose at the start to force a win, and \(M(n) = 0\) if there is no such move. For example, \(M(2) = 2\), \(M(7) = 1\), and \(M(20) = 4\).

It can be verified that \(\sum{M(n)^3} = 8150\) for \(1 \le n \le 20\).

Find \(\sum{M(n)^3}\) for \(1 \le n \le 1000\).

解决方案

题目定义：\(s_k\)是把\(0,1,2,\dots,k\)写成二进制后，出现的\(1\)的总数。令 \(b(x)\) 表示 \(x\) 的二进制中 \(1\) 的个数，则显然\(\displaystyle{s_k=\sum_{i=0}^{k}b(i)}\)，从而差分非常简单：\(s_{k+1}-s_k=b(k+1)\)，因此 \(s\) 是严格递增序列。

游戏中计数器 \(c\) 必须始终属于 \(S\)。由于 \(S\) 递增，任何时刻 \(c\) 都可唯一写为某个 \(s_k\)。若当前 \(c=s_k\)，玩家选择 \(d\in[1,n]\) 后必须满足：\(s_k+d\in S\)即存在某个 \(t\ge 1\) 使得：\(s_{k+t}=s_k+d\)

因此走法等价于从索引 \(k\) 跳到某个更大的索引 \(k+t\)，并且步长满足：\(d=s_{k+t}-s_k\le n\)。又因为\(\displaystyle{s_{k+t}-s_k=\sum_{i=k+1}^{k+t}b(i)}\)，所以从 \(k\) 可到达的索引集合恰为一段连续区间：\(\{k+1,k+2,\dots,k+C_k\}\)，其中 \(C_k\) 是满足\(\displaystyle{\sum_{i=k+1}^{k+C_k}b(i)\le n,\sum_{i=k+1}^{k+C_k+1}b(i)>n}\)的最大整数。

可见，该游戏是标准无偏博弈，设状态 \(s_k\) 的 SG 值为 \(G_k\)，则：

\[ G_k=\operatorname{mex}\{G_{k+1},G_{k+2},\dots,G_{k+C_k}\} \]

其中\(\operatorname{mex}\)表示不在集合中的最小非负整数。起点是 \(c=0=s_0\)，即 \(k=0\)。若 \(G_0=0\) 则先手必败，此时 \(M(n)=0\)。

若 \(G_0\ne 0\)，先手必赢，且任何必赢首步必须跳到一个 SG 值为 \(0\) 的后继状态。由于从 \(0\) 出发可到达的状态是连续区间：\(\{s_1,s_2,\dots,s_{C_0}\}\)。若存在唯一的 \(i\in[1,C_0]\) 满足 \(G_i=0\)，则先手唯一必赢的首步为\(M(n)=s_i\)。

由于可达后继是一段连续区间，且\(G_k\) 是窗口中后继一系列的SG值集合取mex运算后的结果，因此窗口每向前移动一步（从 \(k\) 变为 \(k+1\)），其结构是删去左端一个元素，再向右扩展若干个元素来维持步长限制 \(\le n\)。

核心结论是：在这一类连续窗口 mex 递推中，窗口中 SG 值为 \(0\) 的位置最多只有1个。可以用反证法证明：如果存在\(0<i<j<=C_k\)使得\(G_{k+i}=G_{k+j}=0\)，那么由于窗口的右端点是单调递增的，因此\(G_{k+j}\)一定在\(G_{k+i}\)的窗口里。因此如果\(G_{k+j}=0\)，那么按照mex递推的定义，\(G_{k+i}\)不可能为\(0\)。因此，窗口里最多只存在一个\(0\)。所以整个问题只需要知道：当前窗口里是否存在 \(0\)，若存在，\(0\) 在窗口中的相对位置是第几个。

可见，\(G_k\) 是由其后继窗口 \(\{G_{k+1},\dots,G_{k+C_k}\}\) 通过 \(\operatorname{mex}\) 递推确定的，因此它始终依赖于更靠后的状态。特别地，在起点 \(k=0\) 处我们既不知道 \(G_0\) 的值，也不知道可达窗口 \(W_0=\{G_1,\dots,G_{C_0}\}\) 中是否存在 \(0\)，更无法预先确定 \(0\) 出现在哪个位置。于是只能将“窗口内 \(0\) 的位置”视为未知量，并对其所有可能取值同时进行追踪：即把 \(x_0\in\{0,1,\dots,n\}\) 的 \(n+1\) 种情形作为初始假设并行推进。

于是我们用一个整数状态变量 \(x\in[0,n]\) 表示当前追踪到的 \(0\) 所在的位置（\(x=0\) 表示窗口中无 \(0\)）。更精确地，对每个 \(k\)，记\(W_k={G_{k+1},G_{k+2},\dots,G_{k+C_k}}\)为从 \(s_k\) 出发的一步可达窗口，其中 \(C_k\) 为窗口长度。由于窗口内 \(0\) 至多出现一次，若存在唯一的 \(p_k\in[1,C_k]\) 使得\(G_{k+p_k}=0,\)则定义\(x_k=C_k+1-p_k,\)即 \(x_k\) 表示“\(0\) 距离窗口右端的反向位置编码”（从右端数的等价坐标）；若窗口中不存在 \(0\)，则定义\(x_k=0.\)

在此定义下，窗口向前移动（从 \(k\) 变为 \(k+1\)）时，左端元素被删去，同时右端会补进若干新元素以维持步长限制 \(\le n\)，从而使得编码 \(x_k\) 发生一次“平移并截断”的更新：\(x_{k+1}\leftarrow \Phi_t(x_k),\)

其中 \(t\) 表示该步窗口右端延展所带来的净平移量，而截断加法算子 \(\Phi_t\) 定义为：

\[ \Phi_t(x)= \begin{cases} x+t,& x+t\le n\\ 0,& x+t>n \end{cases}. \]

直观意义是，窗口向前移动时，相对位置会向右平移若干步；如果超过 \(n\)（意味着在可达范围外），则重置为 \(0\)。因此整个博弈胜负信息可以被压缩成若干次 \(\Phi_t\) 的复合。

直接逐步处理每个\(b(i)\)仍然很慢，但 \(b\) 在 \(2\) 的幂附近具有自相似结构。对 \(0\le x<2^m\) 有：\(b(2^m+x)=b(x)+1\)。

因此，若把区间 \([0,2^{m+1})\) 分成两半 \([0,2^m)\) 与 \([2^m,2^{m+1})\)，则后半段的 \(b\) 序列等于前半段整体加 \(1\)。这一点使得按顺序累加 \(b\) 直到超过 \(n\)的过程可以按块递归组织。

为描述游戏状态的演化，引入有限状态空间：\(X=\{0,1,2,\dots,n\}\)，把处理一段 \(b\) 序列所造成的整体影响抽象成函数复合：对每个块规模 \(m\) 与偏移参数 \(t\)，定义映射\(F_{m,t}:X\to X\)。其含义是：处理一段长度为 \(2^m\) 的 \(b\) 序列块（并整体叠加偏移 \(t\)）后，状态从 \(x\) 变为 \(F_{m,t}(x)\)（也就是\(F_{m,t}=\Phi_{b(2^m-1)+t}\circ \cdots \circ \Phi_{b(1)+t}\circ \Phi_{b(0)+t}.\)是一个复合函数）。

由于二分结构中后半块 = 前半块 + 1，可以得到如下递推：

\[ F_{m,t}(x)=F_{m-1,t}(\Phi_t(F_{m-1,t+1}(x))). \]

这个式子表达了三件事：

• 先处理高半块，它对应偏移 \(t+1\)；
• 高半块结束后，状态需再经过一次截断平移 \(\Phi_t\)；
• 再接上低半块，即偏移 \(t\) 的同规模块。

从而把规模翻倍的演化归约为两个规模减半的演化。这正是倍增的核心：通过反复使用上述递推，可以在对数层数内构造出覆盖极长区间的复合变换。

为了高效地实现大量 \(F_{m,t}\) 的函数复合，可以在二维指标集上组织递推。令\(w=n+1,\)并考虑指标对 \((s,m)\) 其中 \(1\le m\le s\le w\)。定义一族映射\(T_{s,m}:X\to X,\)并规定边界条件为恒等映射：\(T_{s,0}(x)=x.\)

递推规则为：

\[ T_{s,m}(x)=T_{s-1,m-1}(\Phi_{s-m+1}(T_{s,m-1}(x))), 1\le m\le s. \]

该式可以理解为一个“逐步拼接块”的过程：每次把一个新的截断平移 \(\Phi_{s-m+1}\) 插入到既有演化的中间，并与上一层（\(s-1\)）的结构相耦合，从而形成更大的复合变换。

把它写成纯粹的函数复合形式就是：\(T_{s,m}=T_{s-1,m-1}\circ \Phi_{s-m+1}\circ T_{s,m-1}.\)

在这个框架下，所需的候选答案正是每一层最右端的映射值：候选\(M(n)\)由\(T_{s,s}(0)\)给出。

注意到 \(X\) 是有限集合，而 \(T_{s,s}:X\to X\) 是 \(X\) 上的自映射。若某一层出现 常量映射，即存在某个 \(c\in X\) 使得\(T_{s,s}(x)=c, \forall x\in X,\)

则该层的输出已经完全与初始状态无关，意味着所有潜在分支已经收敛到同一个确定结果。于是此时可以立刻确定答案为：\(M(n)=T_{s,s}(0)=c.\)用等价条件写就是：\(T_{s,s}(0)=T_{s,s}(1)=\cdots=T_{s,s}(n).\)

由于之后继续增加规模相当于继续与某些映射复合，而常量映射与任何映射复合仍为常量映射，因此一旦达到这一状态便不可能再改变，因而可以安全早停。

实践中，达到常量映射所需的 \(s\) 通常很小，从而整体计算非常可控。

代码

import numpy as np
N = 1000

def M(n: int) -> int:
    step = n + 1
    M1 = np.empty((step + 1, step), dtype=np.int32)
    M2 = np.empty_like(M1)

    M1[0] = np.arange(step, dtype=np.int32)
    M2[0] = M1[0]

    for s in range(1, step + 1):
        for m in range(1, s + 1):
            inc = s - m + 1
            v = M2[m - 1] + inc
            v[v >= step] = 0
            M2[m] = M1[m - 1][v]

        row = M2[s]
        if np.all(row == row[0]):
            return int(row[0])

        M1, M2 = M2, M1

    return int(M1[step, 0])

ans = sum(M(n) ** 3 for n in range(1,N+1))
print(ans)