Daizhenyang's Coin HDU - 3537

Daizhenyang’s Coin HDU - 3537

题意： 若干个个硬币排成一排，其中有n个是正的，其它都是反的，每一次你可以选择1,2,3 个进行反转，但是最右边的硬币必须是从正面到反面
SG函数可以用来求组合博弈问题

1. 博弈的人数是两个
2. 有限步内结束
3. 每个状态的胜负与人无关

本题是Game theory 论文里面例题
首先由x1,x2,x3 位置的硬币为正，那么他们满足 $SG(x_1,x_2,x_3)=Sg\left(x_1\right)\oplus SG\left(x_2\right)\oplus SG\left(x_3\right)$SG(x1​,x2​,x3​)=Sg(x1​)⊕SG(x2​)⊕SG(x3​)

怎么求SG(x) 的值呢
经过打表发现SG(x) 的函数值不是2x+1,就是2x,这个规律是什么呢？

position x : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
g(x) : 		 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 ... 

定义两个数,暂且称之为 O( odious )，E(evil)，
O: 代表x的二进制表达里面有奇数个1
E: 代表x的二进制表达里面有偶数个1

有一些特殊的库函数用G++编译的时候支持以下操作
__builtin_parity(a) 直接返回a的二进制表达中1的个数的奇偶性，如果有奇数个，返回1，否则返回0

O，E有以下运算法则
$O\oplus O=E,E\oplus E=E$O⊕O=E,E⊕E=E
$O\oplus E=O,E\oplus O=O$O⊕E=O,E⊕O=O
我们发现SG(x) 的值是第x个O数
结论如下：

1. 如果2 * x是O数，SG函数值为2*x
2. 如果2 * x是E数， SG函数值是2*x+1

证明：

没有硬币是正的，终止态，SG = 0，是E数
最左边的硬币（位置从0开始）是的正的 $SG(0）=1$SG(0）=1，是O数
假设对于前x的个数满足证明，对于第x个数的SG值
选择反转一个硬币到终止态SG(0) = 0
选择反转两个硬币，则可以转移到 $SG\left(1\right),SG\left(2\right),SG\left(3\right)......SG(x-1)$SG(1),SG(2),SG(3)......SG(x−1)，是小于2x的所有O数
选择反转三个硬币，是 $SG\left(i\right)\oplus SG\left(j\right)i!=ji,j\&lt;x$SG(i)⊕SG(j)i!=ji,j<x，是小于等于2x的所有E数
所以有结论

1. 如果2 * x是O数，SG函数值为2*x
2. 如果2 * x是E数， SG函数值是2*x+1

参考代码

int main(void)
{
   int n;
   while(cin>>n){
      int sum = 0;
      map<int,int> ma;
      for(int i = 0;i < n; ++i){
         int a;
         scanf("%d",&a);
         if(ma[a]) continue;
         ma[a] = 1;
         if(__builtin_parity(2*a))
            sum ^= 2*a;
         else
            sum ^= 2*a+1;
      }
      if(sum == 0)
         puts("Yes");
      else
         puts("No");
   }
    

   return 0;
}