Project Euler 344
Project Euler 344
题目
Silver dollar game
One variant of N.G. de Bruijn’s silver dollar game can be described as follows:
On a strip of squares a number of coins are placed, at most one coin per square. Only one coin, called the silver dollar, has any value. Two players take turns making moves. At each turn a player must make either a regular or a special move.
A regular move consists of selecting one coin and moving it one or more squares to the left. The coin cannot move out of the strip or jump on or over another coin.
Alternatively, the player can choose to make the special move of pocketing the leftmost coin rather than making a regular move. If no regular moves are possible, the player is forced to pocket the leftmost coin.
The winner is the player who pockets the silver dollar.
A winning configuration is an arrangement of coins on the strip where the first player can force a win no matter what the second player does.
Let \(W(n,c)\) be the number of winning configurations for a strip of \(n\) squares, \(c\) worthless coins and one silver dollar.
You are given that \(W(10,2) = 324\) and \(W(100,10) = 1514704946113500\).
Find \(W(1 000 000, 100)\) modulo the semiprime \(1000 036 000 099 (= 1 000 003 \cdot 1 000 033)\).
解决方案
令总硬币数\(C=c+1.\)注意这里 \(c=100\) 为偶数，因此\(C=101=2f+1, f=\dfrac c2=50\)。注意，\(C\)为奇数枚硬币的情形，因此胜负判据会化成“bogus Nim”。
把硬币从左到右编号，位置为\(1\le x_1<x_2<\cdots<x_{2f+1}\le n.\)定义相邻硬币之间的空格数（含边界）：
- 左端空格 \(g_0=x_1-1\)
- 中间空格 \(g_i=x_{i+1}-x_i-1 (1\le i\le 2f)\)
- 右端空格 \(g_{2f+1}=n-x_{2f+1}\)
显然\(\displaystyle{g_i\ge 0, \sum_{i=0}^{2f+1} g_i = n-(2f+1)=n-C.}\)
把这些空格分成两类：
- 重要空格：\(g_0,g_2,g_4,\dots,g_{2f}\)（一共 \(f+1\) 个）
- 不重要空格：\(g_1,g_3,\dots,g_{2f-1},g_{2f+1}\)（一共 \(f+1\) 个）
直觉：重要空格对应“成对硬币”之间的缝，会决定胜负；不重要空格只是在“对与对”之间塞空间，对胜负无影响，只影响计数。
现在开始进行胜负判据，注意这里不需要计算出完整的\(SG\)值，只需要判定“轮到走的人是必胜还是必败”。
令总硬币数为 \(2f+1\)。讨论银币相对最左端的两种关键情况：
银币是从左数第 2 枚
此时如果有人选择“把最左硬币装进口袋（special move）”，会立刻把银币暴露成最左硬币，下一手对方直接装走银币获胜——等价于自杀操作。最优策略下可视为 special move 不会被主动使用（除非被迫，但被迫时结果也一致）。为了统一描述，把左边界当作一个“不能越过”的虚拟硬币 \(x_0=0\)，并定义\(y_i = x_{2i+1}-x_{2i}-1 (i=0,1,\dots,f).\)那么\(y_0=g_0, y_i=g_{2i}(i\ge 1),\)即 \(y\) 正好就是“重要空格”的集合。
可见，增大 \(y_i\) 本身是一种无效赠送动作——你把空间让出来，对手马上在同一对里把它吃回去（把局面拉回你增大前）。这种动作即使因为不重要空格大而能做得更多，也只是给对手更多无意义的应对空间，不会改变谁能强制赢。
银币是从左数第 3 枚或更靠右
这时 special move（装走最左硬币）并不立刻输；它更像“把最左硬币移到条带左侧外面”，对后续博弈有结构性的影响。
为把 special move 纳入同一套判据，引入另一种虚拟边界：\(x_0=-1,\)同样定义\(y_i = x_{2i+1}-x_{2i}-1.\)这会让\(y_0 = x_1-(-1)-1 = x_1 = g_0+1, y_i=g_{2i}(i\ge 1).\)也就是这个情况下，第一堆 \(y_0\) 比真实左端空格多 \(1\)。也就是说，这种情况下，我们虚拟了一枚\(x_0=-1\)的硬币在这个边界位置。这种情况你进行special move就相当于把硬币移动到了位置\(0\)，\(-1\)是虚拟边界。
在上述定义下（情况 1 用 \(x_0=0\)，情况 2 用 \(x_0=-1\)），当银币不是最左硬币时：后手必胜当且仅当\(\displaystyle{\bigoplus_{i=0}^f y_i= 0}\)。其中 \(\oplus\) 是按位异或。
证明思路如下：
观察第 \(i\) 对（对应 \(x_{2i}\) 与 \(x_{2i+1}\)）：
- 若移动左边那枚 \(x_{2i}\) 往左 \(d\) 格，则 \(x_{2i}\) 变小，二者间距增大，因而 \(y_i\gets y_i + d.\)
- 若移动右边那枚 \(x_{2i+1}\) 往左 \(d\) 格，则二者间距减小，因而 \(y_i\gets y_i - d, 0\le d\le y_i.\)
并且这类移动不会改变其它 \(y_j\)；它只会在“不重要空格”里做补偿式变化，但我们将看到这些不影响胜负判定。
假设轮到先手走，且当前满足\(\displaystyle{Y=\bigoplus_{i=0}^f y_i = 0.}\)
先手做一个正规移动，只会改变某个 \(y_k\)。
若先手让某个 \(y_k\) 变大（通过移动 \(x_{2k}\)），后手直接把同一对里的右硬币 \(x_{2k+1}\) 往左移动同样的 \(d\)，把 \(y_k\) 原样降回去，所有 \(y_i\) 复原，仍然 \(Y=0\)。合法性来自于：右硬币最多只能移动到与左硬币相邻处，恰好能抵消这次增加。
若先手让某个 \(y_k\) 变小（通过移动 \(x_{2k+1}\)），则在 Nim 中必有唯一的目标值\(y_k'=y_k\oplus Y'\)（这里\(Y'\ne 0\)是先手走后新的异或值）满足 \(y_k'<y_k\) 且把它改成 \(y_k'\) 会令异或归零。在棋盘上，这对应“把右硬币 \(x_{2k+1}\) 往左移动 \(y_k-y_k'\) 格”，显然不跨越 \(x_{2k}\)，因此合法。
因此：从 \(Y=0\) 出发，后手总能在一回合内把局面拉回到 \(Y=0\)。
我们接下来证明 special move 也被这套判据正确处理
情况 1（银币第二）：special move 等价于立刻送死，因此不会成为把 \(Y=0\) 打破并获利的手段；判据只需覆盖正规移动即可。
情况 2（银币第三或更右）：special move 是“装走最左硬币”。在 \(x_0=-1\) 的表示里，装走 \(x_1\) 后，新的最左硬币变成原来的 \(x_2\)，而 \(y_1,\dots,y_f\) 结构保持；同时原本\(y_0=g_0+1>0\)会在新局面中变成“边界紧贴最左硬币”的效果，相当于让第一堆变为 \(0\)。这正是把某一堆改成更小值的 Nim 操作（把 \(y_0\) 改成 \(0\)）。
因此 special move 也不会破坏“\(\displaystyle{\bigoplus_{i=0}^f y_i}\) 决定输赢”的结论。
综上：当银币不是最左时，局面输赢由 \(\displaystyle{\bigoplus_{i=0}^f y_i}\) 是否为 \(0\) 决定；\(\displaystyle{\bigoplus_{i=0}^f y_i}\) 为必败（轮到走的人输），否则必胜。
接下来开始计算方案总数。
总摆放数（先选 \(C\) 个位置，再指定银币是哪一枚）为\(T = C\dbinom{n}{C}.\) 银币如果是最左硬币，先手直接 special move 立刻获胜，这部分已包含在 \(T\) 中，不需要特判；我们只需要数出先手必败的配置并从 \(T\) 中减去。先手必败等价于后手必胜，即上节判据成立且银币不是最左。
我们将必败分成两类：
- \(L_2\)：银币为第 \(2\) 枚（情况 1），且 \(\displaystyle{\bigoplus_{i=0}^f y_i}\)
- \(L_{\ge 2}\)：银币不是前两枚（情况 2），且 \(\displaystyle{\bigoplus_{i=0}^f y_i}\)
最终 \[W(n,c)=T-L_2-(C-2)\cdot L_{\ge 2},\] 因为当银币不在前两枚时，在同一组“硬币位置集合”上，银币可以是第 \(3\) 到第 \(C\) 枚中的任意一枚，共 \(C-2\) 种指定方式，并且胜负判据对“第 \(3\) 枚或更右”只依赖“不是前两枚”，不依赖具体是第几枚。
令 \(f=c/2\)。重要空格（Nim 堆）共有 \(t=f+1\) 堆：\((y_0,y_1,\dots,y_f).\)设\(\displaystyle{D_t(K)=\#\left\{(y_0,\dots,y_{t-1})\in\mathbb Z_{\ge0}^t:\bigoplus_{i=0}^{t-1} y_i=0,\sum_{i=0}^{t-1} y_i=K\right\}}.\)
不重要空格共有 \(f+1\) 个，和为“总空格数减去重要空格和”。因此总空格数：\(S=n-C=n-(2f+1).\)
情况 1：\(y_0=g_0\)，重要空格和为 \(\displaystyle{K=\sum_{i=0}^{t-1} y_i}\)，则不重要空格总和为 \(S-K\)。分配方法数为\(\dbinom{(S-K)+(f+1)-1}{(f+1)-1}=\dbinom{S-K+f}{f}.\)因而
\[L_2=\sum_{K=0}^{S} D_{f+1}(K)\binom{S-K+f}{f}.\]
情况 2：\(y_0=g_0+1\)，所以真实占用的“重要空格”是 \((y_0-1)+y_1+\cdots+y_f = K-1\)。因此不重要空格总和为 \(S-(K-1)=S-K+1\)，分配方法数为\(\dbinom{S-K+1+f}{f}=\dbinom{S-K+f+1}{f}.\)另外情况 2 需要 \(y_0\ge 1\)。把它转成“去掉 \(y_0=0\) 的情况”：若 \(y_0=0\)，则剩下 \(f\) 堆仍需异或为 \(0\) 且和为 \(K\)，数量是 \(D_f(K)\)。因而满足 \(y_0\ge1\) 的数量是 \(D_{f+1}(K)-D_f(K)\)，于是 \[L_{\ge 2} =\sum_{K=0}^{S+1}\bigl(D_{f+1}(K)-D_f(K)\bigr)\binom{S-K+f+1}{f}.\]
核心观察：若 \((y_0,\dots,y_{t-1})\) 异或为 \(0\)，则最低位（奇偶性）必须有偶数个 \(1\)，也就是奇数项个数必须为偶数。
把每个 \(y_i\) 写成\(y_i = 2z_i + b_i, b_i\in{0,1}.\)则
- \(\displaystyle{\bigoplus_{i=0}^{t-1} y_i=0}\) 等价于：\(\displaystyle{\sum_{i=0}^{t-1}b_i}\) 为偶数，且 \(\displaystyle{\bigoplus_{i=0}^{t-1} z_i=0}\)（把所有数右移 \(1\) 位后异或仍为 \(0\)）。
- \(\displaystyle{\sum_{i=0}^{t-1}y_i=2\sum_{i=0}^{t-1}z_i+\sum_{i=0}^{t-1}b_i}\)。
因此若我们已知“右移后”的和为 \(\displaystyle{\sum_{i=0}^{t-1}z_i=s}\)，并选择其中恰好 \(e\) 个 \(b_i=1\)（必须 \(e\) 为偶数），则原和变为 \(2s+e\)，对应组合数 \(\dbinom{t}{e}\)。
因此我们可以写出如下关于\(D_t(K)\)的转移过程：
- 初始：全为 \(0\) 的序列唯一，\(D_t(0)=1\)。
- 转移：对每个当前的 \(s\)，把它扩展到 \(2s+e\)（\(e\) 为偶数）：\(D_t(2s+e)\leftarrow D_t(s)\dbinom{t}{e}.\)
由此最终计算出\(D_{f}(\cdot), D_{f+1}(\cdot)\)后，即可计算出\(L_2,L_{\ge 2}\)，并构造出最终的结果\(W(n,c)\)。
代码
1 | from typing import List |