洛谷P2252 【模板】威佐夫博弈题解

题目链接：P2252 [SHOI2002] 取石子游戏|【模板】威佐夫博弈

题意：

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。

游戏规定，每次有两种不同的取法：

一是可以在任意的一堆中取走任意多的石子；

二是可以在两堆中同时取走相同数量的石子。

最后把石子全部取完者为胜者。

现在给出初始的两堆石子的数目，你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

输入格式：

输入共一行。

第一行共两个数 $a, b$ ，表示石子的初始情况。

输出格式：

输出共一行。

第一行为一个数字 $1,0$ 或 $-1$ ，如果最后你是胜利者则为 $1$ ；若失败则为 $0$ ；若结果无法确定则为 $-1$ 。

数据范围：

对于 $100\%$ 的数据满足 $0\le a, b \le 10^9$ 。

定义后手必胜态为奇异局势（~~什么鬼名字？~~），容易列举出一些这样的状态

$\begin{aligned} & 0:(0,0) \\[6pt]& 1:(1,2) \\[6pt]& 2:(3,5) \\[6pt]& 3:(4,7) \\[6pt]& 4:(6,10) \\[6pt]& 5:(8,13) \end{aligned}$

首先 $(0,0)$ 显然是奇异局势。考虑 $(1,2)$ 的情况

如果先手取走 “1” 中的 1 个，那么后手就从 “2” 中取出 2 个，此时取完，后手胜利。
如果先手取走 “2” 中的 2 个，那么后手取走 “1” 中的 1 个，此时取完，后手胜利。
如果先手取走 “2” 中的 1 个，那么后手就在两堆中各取走 1 个，此时取完，后手胜利。
如果先手在 “1” 和 “2” 各取走了 1 个，那么后手取走 “2” 中的 1 个，此时取完，后手胜利。

故 $(1,2)$ 为奇异局势。其余情况证明略。

注意到每个奇异局势都形如 $(x, \, x + k)$ ，并且 $x$ 均为即之前未出现过的最小自然数。

形式化的，对于奇异局势 $(x_i,y_i)$ 均有 $y_i=x_i + i$ 和 $x_i = \operatorname{mex}\{x_1,y_1,\cdots,x_{i-1},y_{i-1}\}$ 。

这个规律的证明啥的我就不证了，详细的证明太长了而且也没啥用。

可以发现由于 $x_i$ 是 $\operatorname{mex}$ ，因此形如 $(x_i,y_i)$ 奇异局势将全体整数划分为两个不相交的集合。

这其实也进一步说明了所有奇异局势都是以上 $(x_i,y_i)$ 的形式。

下面引入 Beatty 定理（Beatty sequence）：

若 $p,q \in \mathbb{R}^+$ 且 $p,q \not\in \mathbb{Q}$ （也就是两个正无理数 $p,q$ ）满足 $\frac{1}{p}+\frac{1}{q}=1$ ，

则集合 $P=\left\{\lfloor n p\rfloor: n \in \mathbb{Z}^{+}\right\},~Q=\left\{\lfloor n q\rfloor: n \in \mathbb{Z}^{+}\right\}$ 满足 $P \cap Q=\varnothing, P \cup Q=\mathbb{Z}^{+}$ 。

~~还是一样~~，证明我就不证了。

我们发现，相邻奇异局势的差值 $x_i - x_{i-1}$ 通常是 $1$ 或 $2$ ，但似乎没有规律可言。

我们可以认为第一个数构成集合 $P=\left\{\lfloor an\rfloor: n \in \mathbb{Z}^{+}\right\}$ ，

由 $y_i$ 的定义可知第二个数构成集合 $Q=\left\{\lfloor (a+1)n\rfloor: n \in \mathbb{Z}^{+}\right\}$ 。

由于 $P,Q$ 满足 $P \cap Q=\varnothing, P \cup Q=\mathbb{Z}^{+}$ 即构成正整数集的一个分划

所以 $\frac{1}{a}+\frac{1}{a+1}=1$ ，解方程可得

$\begin{aligned} & \Delta=5 \\ & a_1=\frac{1+\sqrt{\Delta}}{2}, a_2=\frac{1-\sqrt{\Delta}}{2} \end{aligned}$

因为 $a > 1$ ，所以 $a = \frac{1+\sqrt{5}}{2}$ ，那么第 $k$ 个奇异局势为 $(\left\lfloor ak\right\rfloor,\left\lfloor (a+1)k\right\rfloor)$ 。

那么对于本题，假设 $n \le m$ ，先手必胜当且仅当

$n \ne \frac{1+\sqrt{5}}{2}(m - n)$

时间复杂度 $\mathcal{O}(\log V)$

代码：（注意要用 long double 的开方函数 sqrtl ）

cpp

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)())

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    if(n > m) swap(n, m); const int k = m - n;
    cout << (n != (int)((1 + sqrtl(5.0)) / 2.0 * k)) << '\n';
    return 0;
}