Project Euler 711
Project Euler 711
题目
Binary Blackboard
Oscar and Eric play the following game. First, they agree on a positive integer \(n\), and they begin by writing its binary representation on a blackboard. They then take turns, with Oscar going first, to write a number on the blackboard in binary representation, such that the sum of all written numbers does not exceed \(2n\).
The game ends when there are no valid moves left. Oscar wins if the number of \(1\) s on the blackboard is odd, and Eric wins if it is even.
Let \(S(N)\) be the sum of all \(n \le 2^N\) for which Eric can guarantee winning, assuming optimal play.
For example, the first few values of \(n\) for which Eric can guarantee winning are \(1,3,4,7,15,16\). Hence \(S(4)=46\).
You are also given that \(S(12) = 54532\) and \(S(1234) \equiv 690421393 \pmod{1\,000\,000\,007}\).
Find \(S(12\,345\,678)\). Give your answer modulo \(1\,000\,000\,007\).
解决方案
我们固定起始 \(n\)。原游戏中黑板上写了一串数，要求总和不超过 \(2n\)。令
- 当前已写总和为 \(s\)（初始 \(s=n\)）；
- 剩余额度为 \(x=2n-s\)（初始 \(x=n\)）；
- 黑板上所有数的 \(1\) 的总数的奇偶为 \(\sigma\in\{0,1\}\)（初始 \(\sigma=b(n)\bmod 2\)）。
每一步选择写一个 \(t\)，满足 \(1\le t\le x\)，然后\(x\leftarrow x-t, \sigma\leftarrow \sigma\oplus (b(t)\bmod 2).\)
引理1：对任意非负整数 \(a,b\)，设二进制相加 \(a+b\) 时产生的进位次数为 \(C(a,b)\)（从低位到高位，某一位产生进位就计一次），则有\(C(a,b)=b(a)+b(b)-b(a+b),\)其中 \(b(t)\) 是\(t\)的二进制 \(1\) 的个数。
证明要点：不考虑进位时，每一位 \(1+1\) 会贡献 \(2\) 个 \(1\)；发生进位时，\(1+1\) 变成该位 \(0\) 且向高位送出 \(1\)，相当于“\(2\) 个 \(1\) 变成 \(1\) 个 \(1\)”，也就是 \(1\) 的个数减少 \(1\)。累加所有发生进位的位，就得到上式。
立即推论：对 \(x=y+t\)，\(b(t)\equiv b(x)-b(y)+C(y,t)\pmod 2.\)
引理2将描述一个等价的正常态游戏。定义\(\tau=\sigma\oplus (b(x)\bmod 2).\)从状态 \(x\) 走到 \(y<x\)（即写了 \(t=x-y\)）时，由引理 1 推得\(\tau\leftarrow \tau\oplus \bigl(C(y,x-y)\bmod 2\bigr).\)
特别地，起始时 \(x=n,\sigma=b(n)\bmod2\)，所以\(\tau_0=\sigma\oplus b(x)\equiv b(n)\oplus b(n)=0.\)因此：每走一步，\(\tau\) 是否翻转只取决于该步二进制进位次数的奇偶。
而终局时 \(x=0\)，此时 \(b(x)=0\)，所以 \(\tau_{\text{end}}=\sigma_{\text{end}}\)，也就是终局胜负（Oscar 想要 \(\sigma_{\text{end}}=1\)，Eric 想要 \(\sigma_{\text{end}}=0\)）等价于 \(\tau_{\text{end}}\) 的取值。
由于 \(\tau_0=0\)，可见：终局 \(\tau_{\text{end}}=1\) 当且仅当“翻转次数为奇数”；终局 \(\tau_{\text{end}}=0\) 当且仅当“翻转次数为偶数”。
于是我们把原游戏等价为下面这个正常态游戏：状态是一个整数 \(x\ge 0\)。一步操作是选 \(y\) 满足 \(0\le y<x\)，并且要求 \(C(y,x-y)\equiv 1\pmod 2,\) 然后令 \(x\leftarrow y\)。无步可走者输。
所以：原题里Eric 必胜的 \(n\)就是等价正常态游戏中起始状态 \(x=n\) 的必败态。
下面我们只研究等价正常态游戏的必败态集合 \(\mathcal{P}\)。记\(n=2^e+x, 0\le x<2^e.\)
我们要证明此递归刻画：\(n\in\mathcal{P}\) 当且仅当满足其中一个条件：
- \(x=2^e-1\)；
- \(e\) 为偶数且 \(x=0\)；
- \(e\) 为偶数，\(x\in\mathcal{P}\)，且 \(x\ne 2\cdot 4^\ell-1(\ell \ge 0)\)。
我们的证明分两步：先做两个结构引理，然后按 \(e\) 奇偶讨论。
引理3：若 \(n=2^e+x\) 且取 \(y=2^e+z\)（其中 \(0\le z<x\)），则\(C(y,n-y)=C(z,x-z).\)
证明：此时\(n-y=(2^e+x)-(2^e+z)=x-z<2^e,\)因此相加 \(y+(n-y)=(2^e+z)+(x-z)\) 时，在第 \(e\) 位及以上不会出现任何进位（因为低 \(e\) 位的和为 \(x<2^e\)），所有进位完全发生在低 \(e\) 位里，等同于 \(z+(x-z)=x\) 的进位。
所以：在区间 \([2^e,2^{e+1})\) 内“保持最高位不变”的走法，完全等价于对低位部分 \(x\) 的走法。
引理4：对任意 \(k\ge 1\)，令\(n=2^k-1,\)则 \(n\) 无合法走法，故 \(n\in\mathcal{P}\)。
证明：任取 \(0\le y<n\)，有\(n-y=(2^k-1)-y\)等于把 \(y\) 的低 \(k\) 位逐位取反（这是“用全 \(1\) 减去一个数”的经典性质），因此 \(y\) 与 \(n-y\) 在每一位上不可能同时为 \(1\)，也就不会产生进位： \(C(y,n-y)=0,\)与合法性要求“进位数为奇数”矛盾。故无步可走。于是所有 \(2^k-1\) 都是必败态。
接下来我们证明\(n\in \mathcal{P}\)的三种情况。
第一种情况则是当\(x=2^e-1\)时，此时 \(n=2^{e+1}-1\)，由引理 4 得 \(n\in\mathcal{P}\)，从而得证。
接下来第二种情况证明：当\(e\) 为奇数，且 \(x\ne 2^e-1\)时，有 \(n\notin\mathcal{P}\)（即必胜态）。
用反证来证明：如果 \(n\) 是必败态，那么它的所有合法后继都必须是必胜态；反过来，只要我们构造出一个合法后继是必败态，就能推出 \(n\) 为必胜态。构造思路如下：
由于 \(e\) 为奇数，数 \(n=2^e+x\) 的最高位 \(2^e\) 落在奇数下标位上。我们将证明：在 \(x\ne 2^e-1\) 的前提下，总可以构造一个严格小于 \(n\) 的后继 \(y\)，使得 \(y\in\mathcal P\) 且该步转移满足合法性条件。由此可推出 \(n\notin\mathcal P\)。
令\(j=\nu_2(x+1),\)其中 \(\nu_2(\cdot)\) 表示 \(2\)-进阶。等价地，\(j\) 是 \(x+1\) 的二进制末尾连续 \(0\) 的个数。由于 \(0\le x<2^e\) 且 \(x\ne 2^e-1\)，可知 \(x+1\ne 2^e\)，从而\(0\le j\le e-1.\)定义\(y=2^{e-1}+2^{e-3}+\cdots+2^{j+1}.\)因为 \(e\) 为奇数，所以指数 \(e-1,e-3,\dots,j+1\) 全为偶数下标位，故 \(y\) 的二进制展开仅在偶数下标位上取 \(1\)。
根据必败态集合 \(\mathcal P\) 的结构刻画（“只在偶数下标位取 \(1\)”的数属于 \(\mathcal P\) 的第一类），可得 \(y\in\mathcal P\)。接下来只需验证该 \(y\) 的确是 \(n\) 的一个合法后继，即可完成构造并推出 \(n\notin\mathcal P\)。
接下来验证这一步是合法走法：也就是\(C(y,n-y)\equiv 1\pmod2.\)由于 \(y\) 的低 \(j+1\) 位全为 \(0\)，而 \(x+1\) 的低 \(j\) 位全为 \(0\)、第 \(j\) 位为 \(1\)，可以逐位追踪 \(y+(n-y)=n\) 的进位链，得到进位只会在区间 \([j, e-1]\) 中出现且恰好出现 \(e-j\) 次，因此\(C(y,n-y)\equiv e-j\equiv 1\pmod2\)（因为 \(e\) 为奇数，\(j\) 为偶数；这点来自 \(x+1\) 的最低 \(1\) 位位置 \(j\) 与 \(e\) 的奇偶关系）。
于是我们得到了一个合法走法 \(n\to y\)，且 \(y\in\mathcal{P}\)，因此 \(n\) 为必胜态。这就证明了：当 \(e\) 为奇数时，除了全 \(1\) 之外都不是必败态。
接下来考虑\(e\)为偶数的情况。此时最高位在偶数位。结论分成三部分：
当\(x=0\) 时，有\(n=2^e\in\mathcal{P}\)时，也就是第二个条件。
证明：我们展示它存在合法走法且所有合法走法都走到必胜态。对 \(n=2^e\)，任何 \(y<n\) 都落在 \([0,2^e)\)，而 \(n-y\) 的最高位固定为 \(2^e\)，进位行为只由 \(y\) 的形状决定。可以证明此时“进位数为奇数”的 \(y\) 只有一个：\(y=2^{e-1},\)并且 \(2^{e-1}\) 在 \(e-1\) 为奇数的情形下是必胜态（前面已证：奇数最高位的非全 \(1\) 都必胜）。因此 \(2^e\) 只有一条合法边指向必胜态，故 \(2^e\) 为必败态。
当若 \(x\in\mathcal{P}\) 且 \(x\ne 2\cdot 4^\ell-1\)，则 \(n=2^e+x\in\mathcal{P}\)，这是第三个条件的正向。证明分两类后继：
- 保持最高位的后继：即 \(y=2^e+z\)。由引理 3，这等价于 \(x\to z\)。因为 \(x\in\mathcal{P}\)，所以所有合法 \(x\to z\) 都到必胜态 \(z\)，于是对应的 \(y\) 也全是必胜态。
- 丢掉最高位的后继：即 \(y<2^e\)。可以证明当 \(x\ne 2^{2\ell+1}-1\)（也就是你写的 \(2\cdot 4^\ell-1\)）时，所有满足“进位为奇数”的 \(y\) 都落在必胜态集合里（直观上：会迫使 \(y\) 的最高位落在奇数位但又不是全 \(1\)，从而必胜）。
因此 \(n\) 的所有合法后继都是必胜态，故 \(n\) 为必败态。
若 \(x=2\cdot 4^\ell-1\)，则 \(n=2^e+x\notin\mathcal{P}\)，这是第三个条件里的排除项。
证明：当 \(x=2^{2\ell+1}-1\) 时，可以构造一个丢掉最高位的后继\(y=2^{2\ell},\)它属于上一段里“偶数位结构”的必败态集合（第一类），因此 \(y\in\mathcal{P}\)；同时可以逐位计算得到这一步进位次数为奇数，所以是合法走法。于是 \(n\) 存在合法走法到必败态，故 \(n\) 为必胜态。
最终总结：\(n\) 是 Eric 的必胜起始值，当且仅当满足下列之一：
- \(x=2^e-1\)（即 \(n=2^{e+1}-1\) 是全 \(1\) 形）
- \(e\) 为偶数且 \(x=0\)（即 \(n=2^e\) 且 \(e\) 偶）
- \(e\) 为偶数、\(x\) 本身是 Eric 必胜，并且 \(x\) 不能 写成\(x=2\cdot 4^\ell-1(\ell\ge 0).\)
这一条的意义是：当最高位指数 \(e\) 为偶数时，区间 \([2^e,2^{e+1})\) 里的 Eric 必胜态，基本由“把较小的必胜态 \(x\) 平移到 \(2^e+x\)”给出，但要剔除一小串特殊形 \(2\cdot 4^\ell-1\)；另外还总是包含端点 \(2^e\) 与 \(2^{e+1}-1\)。
我们定义\(Q(N)\)：所有 \(n\le 2^N\) 中 Eric 必胜的个数；\(S(N)\)：所有 \(n\le 2^N\) 中 Eric 必胜的数之和。由上面的分解可推出下面两条递推（令 \(N\ge 2\)）：
当 \(N\) 为偶数时，从 \(2^{N-1}\) 扩到 \(2^N\) 时，新出现的 Eric 必胜数恰好是\(2^N, 2^N-1,\)因此
\[ \begin{cases} Q(N)=Q(N-1)+2,\\ S(N)=S(N-1)+\bigl(2^N+(2^N-1)\bigr)=S(N-1)+2^{N+1}-1. \end{cases} \]
当 \(N\) 为奇数时，此时 \(N-1\) 为偶数。新区间 \((2^{N-1},2^N]\) 中的必胜数对应于\(2^{N-1}+x (x\le 2^{N-1})\)，其中 \(x\) 为此前的必胜数。但要剔除\(x\in\left\{2\cdot 4^\ell-1\mid 0\le \ell\le \dfrac{N-1}{2}\right\}.\)这串被剔除的元素个数是\(\dfrac{N+1}{2}.\)于是
\[ Q(N)=Q(N-1)+\left(Q(N-1)-\frac{N+1}{2}\right)=2Q(N-1)-\frac{N+1}{2}. \]
对 \(S(N)\)，新区间贡献为\(\displaystyle{\sum_{x\in W}\bigl(2^{N-1}+x\bigr)=\left(Q(N-1)-\frac{N+1}{2}\right)2^{N-1}+\left(S(N-1)-\sum_{\ell=0}^{\frac{N-1}{2}}\left(2\cdot4^\ell-1\right)\right),}\)
因此
\[ S(N)=2S(N-1)+2^{N-1}Q(N-1)-2^{N-2}(N+1)-\sum_{\ell=0}^{\frac{N-1}{2}}\left(2\cdot 4^\ell-1\right). \]
而\(\displaystyle{\sum_{\ell=0}^{m}\left(2\cdot 4^\ell-1\right)=2\sum_{\ell=0}^{m}4^\ell-(m+1)=2\cdot\frac{4^{m+1}-1}{3}-(m+1),m=\frac{N-1}{2},}\)
代入并整理即可得到等价的显式形式（与常见实现一致）： \[ S(N)=2S(N-1)+2^{N-1}Q(N-1)-\frac{2^{N-1}(3N+13)-(3N+1)}{6}. \]
初值由直接枚举可得：\(Q(1)=1, S(1)=1\)（因为 \(n\le 2\) 时只有 \(n=1\) 为 Eric 必胜）。
把 \(N\) 按奇偶拆开写成 \(N=2m\) 或 \(N=2m+1\)。我们先解 \(Q(N)\)。
令\(A_m=Q(2m).\)由递推\(Q(2m)=Q(2m-1)+2, Q(2m-1)=2Q(2m-2)-m\)合并得\(A_m=2A_{m-1}-(m-2), A_0=Q(0)=0.\)可用归纳验证解为：
\[ Q(2m)=2^m+m. \]
于是
\[ Q(2m+1)=2Q(2m)-(m+1)=2^{m+1}+m-1. \]
按照类似的解法，可以得到\(S\)的闭式满足：
\[ \begin{aligned} S(2m)&=\frac{1}{6}\left(8^m+4^{m+2}-7\cdot 2^m-6m-4\right),\\ S(2m+1)&=\frac{1}{3}\left(4\cdot 8^m+8\cdot 4^m-7\cdot 2^m-3m-2\right). \end{aligned} \]
代码
1 | N = 12345678 |