数学：Nim游戏和SG函数

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

以下的性质是显然的
1.无法移动的状态是必败态 
2.可以移动到必败态的局面一定是非必败态 
3.在必败态做所有操作的结果都是非必败态

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

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

否则

1.可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1); 
2.可选步数为任意步，SG(x) = x; 
3.可选步数为一系列不连续的数，用GetSG()计算

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

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

BZOJ1874

限制步数的NIM游戏

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

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn=15;
 5 int n,m,ans;
 6 bool mark[maxn];
 7 int a[maxn],b[maxn],sg[1005];
 8 void calcsg()
 9 {
10     for(int i=0;i<=1000;i++)
11     {
12         memset(mark,0,sizeof(mark));
13         for(int j=1;j<=m;j++)
14             if(i-b[j]>=0) mark[sg[i-b[j]]]=1;
15         for(int j=0;j<=10;j++)
16             if(!mark[j]) {sg[i]=j;break;}
17     }
18 }
19 int main()
20 {
21     scanf("%d",&n);
22     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
23     scanf("%d",&m);
24     for(int i=1;i<=m;i++) scanf("%d",&b[i]);
25     calcsg();
26     for(int i=1;i<=n;i++) ans^=sg[a[i]];
27     if(ans==0) printf("NO
");
28     else printf("YES
");
29     for(int i=1;i<=n;i++)
30         for(int j=1;j<=m;j++)
31             if(sg[a[i]-b[j]]==(ans^sg[a[i]]))
32             {
33                 printf("%d %d
",i,b[j]);
34                 return 0;
35             }
36     return 0;
37 }