Project Euler 860

题目

Gold and Silver Coin Game

Gary and Sally play a game using gold and silver coins arranged into a number of vertical stacks, alternating turns. On Gary’s turn he chooses a gold coin and removes it from the game along with any other coins sitting on top. Sally does the same on her turn by removing a silver coin. The first player unable to make a move loses.

An arrangement is called fair if the person moving first, whether it be Gary or Sally, will lose the game if both play optimally.

Define \(F(n)\) to be the number of fair arrangements of \(n\) stacks, all of size \(2\). Different orderings of the stacks are to be counted separately, so \(F(2) = 4\) due to the following four arrangements:

You are also given \(F(10) = 63594\).

Find \(F(9898)\). Give your answer modulo \(989898989\)

解决方案

设 Gary 为左手玩家（Left），Sally 为右手玩家（Right）。这是一个典型的非对称博弈，并且每一步都只会删去某一列顶部一段硬币，因此整局游戏是各列的disjunctive sum。题目859介绍了组合博弈的记号的定义和应用，本题继续沿用。

先看基础局面：

• 空列：\(\varnothing=\{|\}=0\)
• 单金币列：\(G=\{0|\}=1\)
• 单银币列：\(S=\{|0\}=-1\)

再看两枚硬币列（从上到下）：

1. \(GG\):Gary 可走到 \(G\) 或 \(0\)，Sally 无法走\(GG=\{0,1|\}=2\)
2. \(SS\):对称地\(SS=\{|0,-1\}=-2\)
3. 上银下金（记作 \(SG\)）:Gary 只能拿底部金币并连同上方一起移除，走到 \(0\)；Sally 只能拿顶部银币，走到 \(G=1\)。\(SG=\{0|1\}=\dfrac12\)
4. 上金下银（记作 \(GS\)）:Gary 拿顶部金币后剩 \(S=-1\)；Sally 拿底部银币会整列清空到 \(0\)。\(GS=\{-1|0\}=-\dfrac12\)

所以每一列（高度 2）等价于数值集合\(\left\{2, \dfrac12, -\dfrac12, -2\right\}.\)

题目定义公平：无论先手是谁，先手都必败。而对 surreal number 的局面有标准结论：

• 总值 \(>0\)：Left（Gary）必赢（无论先后手）。
• 总值 \(<0\)：Right（Sally）必赢（无论先后手）。
• 总值 \(=0\)：先手必败。

而本题每列都是 number，整局是这些 numbers 的和，仍是 number。 故公平当且仅当总和为 \(0\)。

于是 \(F(n)\) 就是从 \(\left\{2, \dfrac12, -\dfrac12, -2\right\}\) 中选 \(n\) 个（按列位置有序）使和为 \(0\) 的方案数。

我们将通过生成函数化简这些情况。将四种取值映射成指数 \(-4,-1,1,4\)（即乘以 2 后再作指数）：\(F(n)=[x^0](x^{-4}+x^{-1}+x+x^4)^n.\)乘上 \(x^{4n}\) 等价为\(F(n)=[x^{4n}](1+x^3+x^5+x^8)^n.\)

又因为\(1+x^3+x^5+x^8=(1+x^3)(1+x^5),\)所以\(F(n)=[x^{4n}](1+x^3)^n(1+x^5)^n.\)展开：\(\displaystyle(1+x^3)^n=\sum_{i=0}^n \binom{n}{i}x^{3i},(1+x^5)^n=\sum_{j=0}^n \binom{n}{j}x^{5j}.\)因此

\[ F(n)=\sum_{\substack{0\le i,j\le n\\3i+5j=4n}} \binom{n}{i}\binom{n}{j}. \]

这已经是 \(O(n)\) 求和：枚举 \(i\)，由\(j=\dfrac{4n-3i}{5}\)判整即可。

代码

from tools import Combinatorics

N = 9898
MOD = 989898989
def solve(n, mod):
    co = Combinatorics(n, mod)
    ans = 0
    i0 = (3 * n) % 5
    for i in range(i0, n + 1, 5):
        t = 4 * n - 3 * i
        if t < 0:
            break
        j = t // 5
        if 0 <= j <= n:
            ans = (ans + co.C(n, i) * co.C(n, j)) % mod
    return ans


print(solve(N, MOD))