Lasker's Nim (HDU 3032)

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

Lasker's Nim游戏：每一轮允许两会中操作之一：①、从一堆石子中取走任意多个，②、将一堆数量不少于2的石子分成都不为空的两堆。

很明显：sg(0) = 0，sg(1) = 1。
状态2的后继有：0，1和（1，1），他们的SG值分别为0，1，0，所以sg(2) =2。
状态3的后继有：0、1、2、（1，2），他们的SG值分别为0、1、2、3，所以sg(3) = 4。

状态4的后继有：0、1、2、3、（1，3）和（2，2），他们的SG值分别为0，1，2，4，5，0，所以sg(4) = 3.

由数学归纳法可以得出

sg(4k)=4k-1;sg(4k+1)=4k+1;sg(4k+2)=4k+2;sg(4k+3)=4k+4;

HDU 3032Nim or not Nim?

http://acm.hdu.edu.cn/showproblem.php?pid=3032

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<map>
#define LL long long
#define N 1000000
#define inf 1<<20
using namespace std;
int main(){
	int t,n;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		int k,ans=0;
		for(int i=0;i<n;i++){
			scanf("%d",&k);
			if(k%4==1||k%4==2)
				ans^=k;
			else if(k%4==0)
				ans^=(k-1);
			else
				ans^=(k+1);
		}
		if(ans)
			puts("Alice");
		else
			puts("Bob");
	}
	return 0;
}