HDU 3537 Daizhenyang's Coin（翻硬币）

硬币）"/>

HDU 3537 Daizhenyang's Coin（翻硬币）

题目链接：.php?pid=3537

题意：一排硬币，每次可以翻转1或2或3枚硬币。要求最右边一个硬币在翻转前必须是正面朝上。求初态对先手是否是必胜态？

思路：参照cxlove的博客里的以及我的理解：（按照题目中的意思位置从0开始编号）

(1)当N==1时，硬币为：正，先手必胜，所以SG[0]=1;

(2)当N==2时，硬币为：反正,所有子状态为：反反，正反，SG值分别为0和1，所以SG[1]=2。

(3)当N==3时，硬币为：反反正，所有子状态为：反反反、反正反、正反反、正正反，SG值分别为0,2，1,3，所以SG[2]=4。

同理可得：SG[3]=7,SG[4]=8。我们称一个非负整数为odious，当且仅当该数的二进制形式的1出现的次数是奇数，否则称作evil。我们发现若2x是odious则SG[x]=2x,否则SG[x]=2x+1(此时2x+1为odious)。也就是所有的SG值均为odious。这样怎么证明呢？我们会发现：

                           evil^evil=odious^odious=evil

                           evil^odious=odious^evil=odious

设现在第n=4个位置上时正面，及反反反正,那么：

（1）若我们只翻转一个，即只翻转最后一个得到反反反反，此时SG值为0；

（2）若我们翻转两个，得到正反反反，反正反反，反反正反，依次为SG[0],SG[1],SG[2]；

（3）若我们翻转三个，那么得到正正反反，正反正反，反正正反，此时前面的3个位置的SG正好是3,5,6，即SG[0]^SG[1],SG[0]^SG[2],SG[1]^SG[2]，我们知道这些数(3,5,6)必定是evil，因为他们由两个odious抑或得到。而且，不可能得到SG[2]后面的一个odious，因为两个odious的抑或值必定是evil。并且他们可以覆盖SG[2]后面的一个odious(即7)之前的除0外的所有evil数(在本例中即3,5,6).为什么呢？SG[2]之后的第一个odious(设为p)含有奇数个1对吧，那么小于p的含有偶数个1的数必定可以拆成两个数odious数的抑或且这两个数均小于p。那么这两个数都是SG[0],SG[1],SG[2]中的数，因此必定这个evil被覆盖。

综上，SG[n]为SG[n-1]之后的第一个odious值。

int C,num=0;
int n,a[105];int main()
{while(scanf("%d",&n)!=-1){if(!n){puts("Yes");continue;}int x=0,i,j,k;for(i=0;i<n;i++) scanf("%d",a+i);sort(a,a+n);n=unique(a,a+n)-a;for(i=0;i<n;i++){k=0;j=a[i];while(a[i]){if(a[i]&1) k++;a[i]>>=1;}if(k&1) x^=2*j;else x^=2*j+1;}if(!x) puts("Yes");else puts("No");}return 0;
}