【BZOJ1299】巧克力棒（Nim游戏，SG函数）

题意：TBL和X用巧克力棒玩游戏。每次一人可以从盒子里取出若干条巧克力棒，或是将一根取出的巧克力棒吃掉正整数长度。

TBL先手两人轮流，无法操作的人输。

他们以最佳策略一共进行了10轮（每次一盒）。你能预测胜负吗？

如果TBL胜则输出”NO”,否则输出”YES”

n<=14,a[i]<=1e9

思路：一个结论：Nim游戏中一个xor和不为0（先手必胜）的状态一定可以通过1步转化为xor和为0（先手必败）的状态

所以先手第一步只需要取出一个xor和为0的最长子序列

若后手选择加入新巧克力棒，先手可以通过1步将已经加入的Nim游戏变为xor和为0的局面

若后手选择取已经加入的部分，先手依然可以通过1步将后手行动过的局面的xor和变为0

所以只需要判断初始局面下存不存在xor和为0的子序列

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 typedef long long ll;

 using namespace std;

 #define N   210000

 #define oo  10000000

 #define MOD 1000000007

 int a[N],b[N],f[N];

 int lowbit(int x)

 {

     return x&(-x);

 }

 int main()

 {

     for(int v=;v<=;v++)

     {

         int n;

         scanf("%d",&n);

         for(int i=;i<=n;i++) scanf("%d",&a[i]);

         int x=;

         for(int i=;i<=n;i++)

         {

             b[x]=i;

             x<<=;

         }

         f[]=;

         for(int i=;i<=(<<n)-;i++) f[i]=f[i^lowbit(i)]^a[b[lowbit(i)]];

         int ans=;

         for(int i=;i<=(<<n)-;i++)

          if(!f[i]) ans=;

         if(ans) printf("NO\n");

          else printf("YES\n");

     }

     return ;

 }