ARC151C 01 Game
题目链接：ARC151C 01 Game
\(SG\) 函数好题。
思路
考虑把原问题分成多个区间的不同问题，求 \(SG\) 在异或起来。
设：
1.\(SG_1(len)\) 长度为 \(len\)，边界没有数字。
2.\(SG_2(len)\) 长度为 \(len\)，只有一个边界有数字。
3.\(SG_3(len)\) 长度为 \(len\)，两个边界都有相同数字。
4.\(SG_4(len)\) 长度为 \(len\)，两个边界都有不同数字。
初始有 \(SG_1(0)=SG_2(0)=SG_4(0)=0,SG_3(0)=1\)。
因为 \(SG_3(0)\) 不存在，所以看做先手胜。
考虑枚举选择的点 \(i\)，有：
\[SG_1(len)=\operatorname{mex}_{i=1}^{len}(SG_2(i-1) \oplus SG_2(len-i)) \]\[SG_2(len)=\operatorname{mex}_{i=1}^{len}\operatorname{mex}(SG_2(i-1) \oplus SG_3(len-i),SG_2(i-1) \oplus SG_4(len-i)) \]\[SG_3(len)=\operatorname{mex}_{i=1}^{len}\operatorname{mex}(SG_3(i-1)\oplus SG_3(len-i),SG_4(i-1) \oplus SG_4(len-i)) \]\[SG_4(len)=\operatorname{mex}_{i=1}^{len}\operatorname{mex}(SG_3(i-1)\oplus SG_4(len-i),SG_4(i-1) \oplus SG_3(len-i)) \]然后我们通过打表发现：
\[SG_1(len)=len\mod 2 \]\[SG_2(len)=len \]\[SG_3(len)=1 \]\[SG_4(len)=0 \]这个可以也可以通过上述方程归纳证明。
CODE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5;
ll n;
ll x[maxn];
int m;
int y[maxn];
int main()
{
scanf("%lld%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%lld%d",&x[i],&y[i]);
x[0]=0,x[m+1]=n+1;
ll sg=0;
for(int i=0;i<=m;i++)
{
ll len=x[i+1]-x[i]-1;
if(i==0&&i==m) sg^=(len&1);
else if(i==0||i==m) sg^=len;
else if(y[i]==y[i+1]) sg^=1;
}
if(sg) printf("Takahashi");
else printf("Aoki");
}