博弈论全家桶

NIM博弈

裸题题意：
有n堆石子，两个绝顶聪明的人轮流操作，每次操作为取走一堆中的若干个石子，取走最后一个石子的人获胜，问先手是否能赢。

这显然是一个公平组合问题——不能行动者败。
显然，当所有堆的石子数为0，必败，此时
$a[1] operatorname{xor} a[2] operatorname{xor}……a[n]=0$ .
不管一个人进行什么样的操作，另一个人总能把异或值调整回来。

所以如果 $a[1] operatorname{xor} a[2] operatorname{xor}……a[n] e 0$ ，
先手给后手一个 $a[1] operatorname{xor} a[2] operatorname{xor}……a[n]= 0$ 的状态，
那么以后每次先手也总能给后手一个 $a[1] operatorname{xor} a[2] operatorname{xor}……a[n]= 0$ 的状态（直到石子数为零）

综上：若 $a[1] operatorname{xor} a[2] operatorname{xor}……a[n] e 0$ ，先手必胜。反之，先手必败。

传送门

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define g getchar()
using namespace std;
int t,n,a,b;
void qr(int &x)
{
	char c=g;x=0;
	while(!('0'<=c&&c<='9'))c=g;
	while('0'<=c&&c<='9')x=x*10+c-'0',c=g;
}
int main()
{
	qr(t);
	while(t-->0)
	{
		qr(n);qr(a);
		while(--n>0)qr(b),a^=b;
		if(a)puts("Yes");
		else puts("No");
	}
	return 0;
}

威佐夫博弈

题意：
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

前置知识：Beatty 定理

内容：
设 $a、b$ 是正无理数且 $dfrac{1}{a} +dfrac{1}{b} =1。$ 记 $P={ lfloor{at} floor | tin N+}，Q={ lfloor{bt} floor | tin N+}$ ，则 $P与Q$ 是 $N+$ 的一个划分，即 $P∩Q$ 为空集且 $P∪Q为正整数集合N+$ 。

证明

$任一个正整数至多在集合P或Q中出现一次因为a、b为正且 dfrac{1}{a} +dfrac{1}{b} =1，$ 则 $a、b>1$ ， $所以对于不同的正整数t，lfloor{at} floor各不相同，类似对b有相同的结果。$ $因此任一个整数至多在集合P或Q中出现一次。$
$现证明P∩Q为空集：(反证法)假设k为P∩Q的一个正整数，则存在正整数m、n 使得lfloor{ma} floor=lfloor{nb} floor=k。即k < ma、nb<k+1，$ 等价地改写不等式为 $dfrac{m}{k+1}< dfrac{1}{a} < dfrac{m}{k}及dfrac{n}{k+1}< dfrac{1}{b} < dfrac{n}{k}$ 。相加起来得
$dfrac{m+n}{k+1} < 1 <dfrac{m+n}{k} ，即 k < m+n < k+1。这与m、n为整数有矛盾，所以P∩Q为空集.$
$现证明N+=P∪Q:$
$已知P∪Q是N+的子集，剩下来只要证明N+是P∪Q的子集。$
$(反证法)假设存在kin N+且k otin P∪Q ，$
$则存在正整数m、n使得lfloor{ma} floor<k <lfloor{(m+1)a} floor、lfloor{nb} floor< k <lfloor{(n+1)b} floor$
$由此得ma < k lelfloor{ (m+1)a} floor-1<(m+1)a -1（因为a是无理数），类似地有nb < k le lfloor{ (n+1)b} floor-1<(n+1)b -1。$
$等价地改写为 dfrac{m}{k} < dfrac{1}{a}< dfrac{m+1}{k+1}及 dfrac{n}{k} < dfrac{1}{b}< dfrac{n+1}{k+1}。两式加起来，得 dfrac{m+n}{k} < 1 < dfrac{m+n+2}{k+1} ，即m+n < k < k+1 < m+n+2。这与m, n, k皆为正整数矛盾。$

设两堆石头个数为 $x,y(xle y)$ .
则必败态如下：

$x$	$y$
0	0
1	2
3	5
4	7
6	10
8	13
……	……

可以发现 $x_i+i=y_i$ , $X，Y为Beatty序列$ .
首先，简单证明一下必败的充分性：
$对于x_i,y_i,令x_i减小或y_i减小或x_i同时减小相同的值都不能到达其他必败态。$

设 $x_i=lfloor{a*i} floor,y_i=lfloor{b*i} floor(dfrac{1}{a} +dfrac{1}{b} =1)$ (满足Beatty定理)
因为 $x_i+i=y_i$
即 $lfloor{ai+i} floor=lfloor{b*i} floor$
$lfloor{(a+1)*i} floor=lfloor{b*i} floor$
所以 $a+1=b$ .
代入 $dfrac{1}{a} +dfrac{1}{b} =1$ ,可得 $a=dfrac{sqrt5+1}{2}$
所以我们就可以得到通项公式了。

传送门
代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int main() {
	int x,y,a;
	while(~scanf("%d%d",&x,&y)) {
		if(x>y)swap(x,y);
		a=(y-x)*1.6180339887498948482045868343656;
		putchar((x!=a)+'0');puts("");
	}
	return 0;
}

博弈论全家桶

NIM博弈

威佐夫博弈

前置知识：Beatty 定理

证明

未完待续……