论如何善用打表神力通过黑题博弈论

Kenton · 2026-10-06 16:31:01 · 算法·理论

人类智慧集 #1 —— 打表猜结论

这里有一道很难的博弈论题 (P6487)

题面

Alice 和 Bob 正在博弈，开始有 N 个石子，第一步 Alice 拿走任意多（不为零）枚石子，随后两人轮流进行：

记上一次拿走了 k 枚石子，当前轮玩家必须拿走 1 至 2k 之间枚石子（具体数量任意）。

拿走最后一枚石子的人胜。

求出 Alice 一开始至少要拿多少石子，才能在双方都足够聪明的情况下必胜。

解法

看到这种博弈论题，像我这种区肯定是做不出来的，于是打表。

先记录 dp_{i, j} 表示 i 枚石子，上一步拿 j 枚的局面状态。

小范围可以 O(n ^ 3) 暴力 DP 算出。

且有：假设初始有 N 枚石子，第一步拿走 k 枚，则这样能胜当且仅当 dp_{N - k, k} = false 。

枚举 N ，暴力求最小 k ，可以得到答案序列： ans = [1, 2, 3, 1, 5, 1, 2, 8, 1, 2, 3, 1, 13 ...] 。

其中， 1, 2, 3, 5, 8, 13 很显眼，并且它们都有 ans_i = i ，可以考虑和 Fibonacci 相关的规律。

列出 ans_{1 ... F_i} （ F_i 为 Fibonacci 数列）:

它们之间有很多公共的子段，动用惊人的注意力（其实也还好），可以发现， T_i = T_{i - 1} + T_{i - 2} 并修改末项为 F_i （ + 是序列拼接， T_i = ans_{1 ... F_i} ）。

题基本就做完了。

最后，对于 N ，怎么不求出 T 的每一项，也能快速求解呢？

利用 T 的递推性，有：

先令 i 为第一个大于等于 N 的 Fibonacci 数。

如果 N = F_i 则答案为 F_i ，否则：

如果 N \le F_{i - 1} 则 i \gets i - 1 ，即走到前半部分。

否则 N \gets N - F_{i - 1}, i \gets i - 2 并继续，即走到后半部分。

如果感兴趣，可以做一下 P6791，思路类似。