[POI2009]石子游戏Kam 【博弈】【分组】★★

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1115
【算法分析】
先假设n为偶数，然后对于任意偶数i<=n，都满足a[i]=a[i-1]。
那么显然先手只能取奇数位置a[j]的石头。然后后手必然可以取同样数量的a[j+1]。那么最后必然是后手的取完石头。所以先手必败。

对于n为偶数时的一般情况，依然是连续的每两个分组。
我们可以将这个模型分成两部分，一部分是a[i-1]=a[i]的，另一部分是a[i]-a[i-1]。（i为偶数）
然后一部分用前面那个解决，后者，将两堆合成一个整体看，就变成一般的NIM游戏了！
于是利用SG函数那个xor定理就可以解决了。。
【CODE】
#include int Tc,n,i,ans,a[1005];
int main(){
scanf("%d",&Tc);
for (;Tc;Tc–){
scanf("%d",&n);
for (i=0;i if (n%2) ans=a[0]; else ans=0;
for (i=n-1;i>0;i-=2) ans^=(a[i]-a[i-1]);
if (ans) puts("TAK");
else puts("NIE");
}
}