Daizhenyang's Coin HDU - 3537

文章目录

Daizhenyang's Coin HDU - 3537

Daizhenyang’s Coin HDU - 3537

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

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

本题是Game theory 论文里面例题
首先由x1,x2,x3 位置的硬币为正，那么他们满足 $S G (x_{1}, x_{2}, x_{3}) = S g (x_{1}) \oplus S G (x_{2}) \oplus S G (x_{3})$

怎么求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 \oplus E = O, E \oplus O = O$
我们发现SG(x) 的值是第x个O数
结论如下：

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

证明：

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

如果2 * x是O数，SG函数值为2*x
如果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;
}