「SDOI2009」E&D - 博弈论+SG函数+阿达马矩阵

题目大意

    桌子上有$2n$堆石子，第$2i-1$堆与第$2i$堆配对。两个人轮流进行操作，每次一个人可以选择一堆石子移走，然后分割其配对的石子，重新形成两堆，所有堆的石子数必须保证大于$0$。
    若其中一方不能再操作时，即石子数全为$1$，该玩家输掉游戏，询问先手是否有必胜策略。

---

题目分析

根据SG定理，$2n$堆石子是$n$个子游戏，因此只需要考虑每个子游戏，其SG函数的异或和情况即为胜败态情况。
而SG函数如何计算？
根据其定义，SG函数为后继状态SG函数的mex。
故：

int SG(int x,int y) {
	if(x==1&&y==1)return 0;
	if(~f[x][y])return f[x][y];
	int vst[1005]= {0};
	if(x>1)for(int i=1; i<=(x>>1); i++)vst[SG(i,x-i)]=1;
	if(y>1)for(int i=1; i<=(y>>1); i++)vst[SG(i,y-i)]=1;
	for(int i=0; ; i++)if(!vst[i])return i;
}

但显然，这样的计算方法会RE,WA,TLE。
因此我们需要寻找更为巧妙的计算方法。

SG函数打个$16\times16$的表：

发现很有规律，是个非常特殊的分形图形，其名字叫做阿达马矩阵。
故可以使用很规律的方法在$\log n$的时间内计算出SG函数。

int SG(int x,int y) {
	if((x&1)&&(y&1))return 0;
	if(x&1)x++;
	if(y&1)y++;
	return SG(x>>1,y>>1)+1;
}

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(isdigit(x)) {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

int SG(int x,int y) {
	if((x&1)&&(y&1))return 0;
	if(x&1)x++;
	if(y&1)y++;
	return SG(x>>1,y>>1)+1;
}

int main() {
	int t=Get_Int();
	while(t--) {
		int n=Get_Int()>>1,ans=0;
		for(int i=1; i<=n; i++) {
			int x=Get_Int(),y=Get_Int();
			ans^=SG(x,y);
		}
		puts(ans?"YES":"NO");
	}
	return 0;
}