Project Euler 859

发表于 2026-02-13 分类于 Project Euler 阅读次数：本文字数： 2.4k 阅读时长 ≈ 2 分钟

Project Euler 859

题目

Odd and Even are playing a game with \(N\) cookies.

The game begins with the \(N\) cookies divided into one or more piles, not necessarily of the same size. They then make moves in turn, starting with Odd.

Odd’s turn: Odd may choose any pile with an odd number of cookies, eat one and divide the remaining (if any) into two equal piles.

Even’s turn: Even may choose any pile with an even number of cookies, eat two of them and divide the remaining (if any) into two equal piles.

The player that does not have a valid move loses the game.

Let \(C(N)\) be the number of ways that \(N\) cookies can be divided so that Even has a winning strategy.

For example, \(C(5) = 2\) because there are two winning configurations for Even: a single pile containing all five cookies; three piles containing one, two and two cookies.

You are also given \(C(16) = 64\).

Find \(C(300)\).

解决方案

把 Odd 看成 Left，Even 看成 Right。一个初始局面是若干堆的disjunctive sum：每步只能在其中一堆上操作。

设 \(G(n)\) 表示单堆大小为 \(n\)对应的 Conway 博弈值。先由题目操作规则写出单堆递推：

若 \(n\) 为奇数：只有 Odd 可动。Odd 吃 1 块后剩 \(n-1\)，平分成两堆 \(((n-1)/2,(n-1)/2)\)，即\(G(2m+1)=\{2G(m)\mid\}\)
若 \(n\) 为偶数：只有 Even 可动。Even 吃 2 块后剩 \(n-2\)，平分成两堆 \(((n-2)/2,(n-2)/2)\)，即\(G(2m+2)=\{\mid 2G(m)\}\)
终止局面：\(G(0)=\{\mid\}=0\)。

每个单堆里始终只有一方有合法步，因此都是冷博弈；递归下去都落在 surreal number 的数里，而且这里全是整数。

记 \(v_n=G(n)\)。

接下来只用 \(\{L\mid R\}\) 的定义：该值是比所有左选项大、且比所有右选项小的最简单数。在本题里只会出现单边选项，因此：

对 \(\{a\mid\}\)：它是“严格大于 \(a\) 的最简单数”。
- 若 \(a<0\)，\(0>a\)，且最简单，故 \(\{a\mid\}=0\)；
- 若 \(a\ge0\)，最简单且 \(>a\) 的整数是 \(a+1\)，故 \(\{a\mid\}=a+1\)。
对 \(\{\mid a\}\)：它是“严格小于 \(a\) 的最简单数”。
- 若 \(a>0\)，\(0<a\)，且最简单，故 \(\{\mid a\}=0\)；
- 若 \(a\le0\)，最简单且 \(<a\) 的整数是 \(a-1\)，故 \(\{\mid a\}=a-1\)。

把 \(a=2v_m\) 代入，得到

\[ v_{2m+1}= \begin{cases} 0, & v_m<0\\ 2v_m+1, & v_m\ge 0 \end{cases}, v_{2m+2}= \begin{cases} 0, & v_m>0\\ 2v_m-1, & v_m\le 0 \end{cases} \]

若初始分堆是分拆\(\displaystyle N=\sum_{i\ge 1} ic_i\)，其总值\(\displaystyle V=\sum_{i\ge 1} c_iv_i.\)由于这些 \(v_i\) 都是整数 surreal 数，和就是普通整数加法。在“Odd 先手”的数值博弈中，Right（Even）有必胜策略当且仅当总值 \(V\le 0\)。因此：

\[ C(N)=\#\left\{(c_i):\sum_{i\ge1} ic_i=N,\sum_{i\ge1} c_i v_i\le0\right\}. \]

问题变成：统计分拆时，按大小权重 \(i\)和价值权重 \(v_i\)同时计数。定义三维状态

\[ F(i,s,t)=\#\left\{(c_1,\dots,c_i)\in\mathbb{Z}_{\ge0}^i\middle|\sum_{k=1}^i kc_k=s,\sum_{k=1}^i v_k c_k=t\right\}. \]

也就是：只允许使用堆大小 \(1\sim i\)，恰好凑出总大小 \(s\)、总价值 \(t\) 的方案数。则有递推

\[ F(i,s,t)= \left\{ \begin{aligned} &1, && \text{if}\quad i=0,s=0,t=0,\\ &0, && \text{if}\quad i=0,(s,t)\neq(0,0),\\ &F(i-1,s,t), && \text{if}\quad i\ge1,s<i,\\ &F(i-1,s,t)+F(i,s-i,t-v_i), && \text{if}\quad i\ge1,s\ge i. \end{aligned} \right. \]

最后答案为

\[ C(N)=\sum_{t\le 0} F(N,N,t). \]

代码

N = 300
def C(N: int) -> int:
    v = [0] * (N + 1)
    for n in range(1, N + 1):
        if n & 1:
            m = (n - 1) // 2
            if v[m] < 0:
                v[n] = 0
            else:
                v[n] = 2 * v[m] + 1
        else:
            m = (n - 2) // 2
            if v[m] > 0:
                v[n] = 0
            else:
                v[n] = 2 * v[m] - 1

    dp = [{0: 1}] + [{} for _ in range(N)]
    for i in range(1, N + 1):
        vi = v[i]
        for s in range(i, N + 1):
            src = dp[s - i]
            dst = dp[s]
            for t, cnt in src.items():
                nt = t + vi
                dst[nt] = dst.get(nt, 0) + cnt

    return sum(cnt for t, cnt in dp[N].items() if t <= 0)


print(C(N))

Project Euler 859

题目

Cookie Game

解决方案

代码