数学：Nim游戏和SG函数

有若干堆石子，两人轮流从中取石子，取走最后一个石子的人为胜利者

以下的性质是显然的

.无法移动的状态是必败态

.可以移动到必败态的局面一定是非必败态

.在必败态做所有操作的结果都是非必败态 

在普通Nim游戏中，a1^a2^a3^……^an=0是必败态

如果没有限制每次可以取走的石子的数量的话，就不用引入SG函数了

否则

.可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+);

.可选步数为任意步，SG(x) = x;

.可选步数为一系列不连续的数，用GetSG()计算 

可以看到第二种情况是SG函数的最简形式，相当于没有引入SG函数

然后打出SG函数表好像就可以做题了

BZOJ1874

限制步数的NIM游戏

然后每一堆的sg函数xor起来得到最终的sg函数，若为0，就输

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int maxn=;

 int n,m,ans;

 bool mark[maxn];

 int a[maxn],b[maxn],sg[];

 void calcsg()

 {

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

     {

         memset(mark,,sizeof(mark));

         for(int j=;j<=m;j++)

             if(i-b[j]>=) mark[sg[i-b[j]]]=;

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

             if(!mark[j]) {sg[i]=j;break;}

     }

 }

 int main()

 {

     scanf("%d",&n);

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

     scanf("%d",&m);

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

     calcsg();

     for(int i=;i<=n;i++) ans^=sg[a[i]];

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

     else printf("YES\n");

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

         for(int j=;j<=m;j++)

             if(sg[a[i]-b[j]]==(ans^sg[a[i]]))

             {

                 printf("%d %d\n",i,b[j]);

                 return ;

             }

     return ;

 }