洛谷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 ）

#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;
}