题解：P2252 【模板】威佐夫博弈 / [SHOI2002] 取石子游戏

William_Y1 · 2025-11-27 11:32:29 · 题解

原题传送门。

写在前面

威佐夫博弈其实没有什么变式，有兴趣的可以看看证明，想要效率的直接记结论就好。

思路

以下为考场可能的思路：

首先我们要明确，两堆石子具有对称性，因此如果石子堆 (a,b) 满足 a>b，我们可以将它转换为 (b,a)。因此，在接下来的探究中，我们默认 (a,b) 满足 a<b。

还是没思路，怎么办咧？

遇事不决先打表呗！

打表代码及结果

以下为部分：

我们将 (a,b) 排序，第 i 组称为 a_i,b_i。

可以看到，随着 i 的增大，b_i-a_i 越来越大，增长不是很明显，但是又不构成等差数列（略大）。

这种性质应该联想到什么啊？

没错应该想到 Fibonacci 数列就很类似。

Fibonacci 数列相邻两项之比约等于 \phi=\dfrac{\sqrt{5}+1}{2}，因此答案有可能跟它有关系。

事实证明我们猜对了。

令 k=b-a，通项公式就是：

a=\lfloor k\phi\rfloor,b=\lfloor k(\phi+1)\rfloor

刚刚说过了，这个公式大家记住就好，别管为什么会想到。

当然，作为严谨的信竞生，我们还是要知道所以然的。

证明

首先我们明确两点。

定理 1：必败态的所有后继都是必胜态。
定理 2：必胜态一定有一个后继是必败态。 :::info[知识点速记：必胜与必败] 必胜态表示当前先手的人存在操作使得其能够赢得游戏。

必败态表示当前先手的人不论怎么操作都不能赢得游戏。

明显游戏的终止状态 (0,0) 是必败态。 ::: 现在我们开始证明刚刚的通项公式，分三步走。

证明内容：令 k=b-a，则 (a,b) 为必败态当且仅当 a=\lfloor k\phi\rfloor（a<b）。

开篇：Beatty 定理

定理简述：设 s,r 是正无理数且 \dfrac{1}{s}+\dfrac{1}{r}=1。记 P=\{\lfloor ks\rfloor |k\in\mathbb{N^+}\},Q=\{\lfloor kr\rfloor |k\in\mathbb{N^+}\}，则 P 与 Q 是 \mathbb{N^+} 的一个划分，即 P\cap Q=\varnothing 且 P\cup Q=\mathbb{N^+}（正整数集）。

证明：

考虑反证。

假设存在正整数 k 满足 k\in P,k\in Q。那么一定存在正整数 n,m 使得 k<ns<k+1,k<mr<k+1（不取等号是因为 ns,mr 一定为无理数）。

于是我们可以进行如下等式变换：

\frac{n}{k+1}<\frac{1}{s}<\frac{n}{k},\frac{m}{k+1}<\frac{1}{r}<\frac{m}{k}\\\ \\ \frac{n+m}{k+1}<\frac{1}{s}+\frac{1}{r}<\frac{n+m}{k}\\\ \\ \frac{n+m}{k+1}<1<\frac{n+m}{k}\\\ \\ n+m<k+1,n+m>k\\\ \\ k<n+m<k+1

这与 n,m,k 为正整数矛盾，故 P\cap Q=\varnothing 成立。

假设存在正整数 k 满足 k\notin P,k\notin Q。那么同样一定存在正整数 n,m 使得 ns<k<k+1<(n+1)s,mr<k<k+1<(m+1)r。

我们可以进行如下等式变换（推导略微跳跃，建议手算一下）：

s<\frac{k}{n},s>\frac{k+1}{n+1},r<\frac{k}{m},r>\frac{k+1}{m+1}\\\ \\ \frac{n}{k}<\frac{1}{s}<\frac{n+1}{k+1},\frac{m}{k}<\frac{1}{r}<\frac{m+1}{k+1}\\\ \\ \frac{n+m}{k}<\frac{1}{s}+\frac{1}{r}<\frac{n+m+2}{k+1}\\\ \\ \frac{n+m}{k}<1<\frac{n+m+2}{k+1}\\\ \\ n+m<k,k+1<n+m+2\\\ \\ m+m<k<k+1<n+m+2

这与 n,m,k 为正整数矛盾，故 P\cup Q=\mathbb{N^+} 成立。

综上，Beatty 定理得证。

过渡：充分性证明

也就是证明：若 a=\lfloor k\phi\rfloor，则 (a,b) 为必败态（a<b，k=b-a）。

其实没法证的……你去试一下就能发现它就是对的……我也说不清楚……

所以我们主要讲它带来的性质。

因为 a=\lfloor k\phi\rfloor,b=\lfloor k(\phi+1)\rfloor，而无理数 \phi,\phi+1 满足 \frac{1}{\phi}+\frac{1}{\phi+1}=1，所以由 Beatty 定理可知，序列 \{\lfloor k\phi\rfloor\},\{\lfloor k(\phi+1)\rfloor\} 构成正整数集的一个划分。也就是说，对于所有必败态 (a,b)，a 和 b 恰好取遍所有正整数一次，b-a 也恰好取遍所有非零整数一次（假设 a,b\not=0）。

由此我们得到，对于一个正整数 a，有且仅有一个正整数 b 使得 (a,b) 为必败态。

终章：必要性证明

也就是证明：若 a\not=\lfloor k\phi\rfloor，则 (a,b) 为必胜态（a<b，k=b-a）。

我们分类讨论。

若 a>\lfloor k\phi\rfloor，则先手玩家可以在两堆石子中各取走 a-\lfloor k\phi\rfloor 颗石子，使得局面变为 (\lfloor k\phi\rfloor,\lfloor k\phi\rfloor+k)，可以证明这是一个必败态，因此此时 (a,b) 为必胜态。

若 a<\lfloor k\phi\rfloor，由“充分性证明”中的结论，对于 a 一定存在一个必败态 (a,a')。若 a>a'，则 a'<a<b。若 a<a'，令 k'=a'-a，则有 a=\lfloor k'\phi\rfloor，又因为 a<\lfloor k\phi\rfloor，所以易得 k'<k，所以 a'=a+k'<a+k=b。因此一定存在 a'<b，因此先手玩家可以从第二堆石子中取走 b-a' 颗石子使局面变为必败态 (a,a')，因此此时 (a,b) 为必胜态。

综上，若 a\not=\lfloor k\phi\rfloor，则 (a,b) 为必胜态（a<b，k=b-a）。

::::info[知识点速记：充分与必要] “充分”就是有利用已知条件足够推出结论，证明时常证明原命题或逆否命题。

“必要”就是推出结论必须要有已知条件，证明时常证明逆命题或否命题。

例如，a=b 是 $	a	=	b	的充分但不必要条件，因为 a=-b 也能得出	a	=	b	$。

综上，令 k=b-a，则 (a,b) 为必败态当且仅当 a=\lfloor k\phi\rfloor（a<b）。证讫。

但是，\phi 是无理数，在 a,b\le10^9 时浮点数的精度误差已经是无法忽视的问题，怎么办呢？

避免精度误差

由于 a=\lfloor k\phi\rfloor，我们可以得到 k\phi-1<a\le k\phi。

我们再次进行等式推导：

a\le k\phi<a+1\\

代入 \phi=\frac{\sqrt{5}+1}{2}：

a\le k\times \frac{\sqrt{5}+1}{2}<a+1\\

同乘 2，移项：

2a\le\sqrt{5}k+k<2a+2\\ 2a-k\le\sqrt{5}k<2a+2-k

最后平方（注意到此时 2a-k>0，因此平方后不等号方向不变）：

(2a-k)^2\le5k^2<(2a+2-k)^2

然后我们就可以快乐地计算啦。

小问题

刚刚我们没有考虑 a=b 的情况，但是可以得到 a=b 时必败态只有 (0,0)（a=0 也只有这一个），并且其余状态都不满足上面的式子，所以我们不需要特判（尝试后得到 (0,0) 也满足上面的表达式）。有惊无险。

当然了： 不开 long long 见祖宗！！！

Code（c++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a, b;

int main() {
    scanf("%lld%lld", &a, &b);
    /*if (a == 0 && b == 0) {
        printf("0\n");
        return 0;
    }*/ // 不用特判！
    if (a > b) swap(a, b);  
    ll k = b - a;
    ll l = (a * 2 - k) * (a * 2 - k);
    ll m = 5 * k * k;
    ll r = ((a + 1) * 2 - k) * ((a + 1) * 2 - k);
    if (l <= m && m < r) printf("0\n");
    else printf("1\n");
    return 0;
}

完结撒花！