CodeForces 603C (Lieges of Legendre)[公平组合博弈，SG函数]

发表于 | 更新于 | | 阅读次数：

题目链接：http://codeforces.com/problemset/problem/603/C

这题是公平组合博弈。对于给定的每堆奶牛，有两种操作，一是减少一只奶牛，二是将奶牛减半并变成k堆。其实第二种操作就相当于游戏分成了许多子游戏，子游戏的SG异或和仍然对应游戏的SG值。
这题最关键的思路是要想到k分奇偶讨论，然后打表找一下规律。

如果k是偶数

当选择2时，有k个n个石子的小堆，状态的sg函数显然为f(n) xor自身 k次=0。
此时我们可以计算得出f(0..4)={0,1,2,0,1}，并且可证明对于n>=2，有f(2n-1)=0，f(2n)=1，化简得f(n)=1-(n%2)，或f(n)=n&1^1。
对于f(2n-1)，我们只能移动到2n-2个石子的状态（游戏1），又f(2n-2)=1>0，所以f(2n-1)=mex{1}=0。
对于f(2n)，可以移动到2n-1的状态（游戏1），或者游戏2，游戏1和2的sg函数值都为0，所以f(2n)=mex{0}=1。

如果k是奇数

此时对于2n个石子的石堆，状态的sg函数为f(n)xor自身k次=f(n)。推导出f(0..5)={0,1,0,1,2,0}。可证明对于n>=2，f(2n)>0，f(2n+1)=0。
对于f(2n+1)，我们只能移动到2n，有f(2n)>0，所以f(2n+1)=0。
对于f(2n)，可以移动到2n-1，f(2n-1)=0，所以f(2n)>0。且f(2n)=mex{f(2n-1),f(n)}=mex{0,f(n)}，递归计算即可。
引用自huanghongxun的博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <cstring>
using namespace std;
int tabe[] = {0,1,2,0,1};
int tabo[] = {0,1,0,1,2,0};
const int maxn=100000;
int getsge(int x) {
	if(x<5) return tabe[x];
	return x&1^1;
}
int getsgo(int x) {
	if(x<6) return tabo[x];
	if(x&1) return 0;
	return getsgo(x/2)==1 ? 2 : 1;
}
int main() {
	int n,k,x;
	int tmp=0;
	scanf("%d%d",&n,&k);
	if(k&1) {
		for(int i=1;i<=n;i++) {
			scanf("%d",&x);
			tmp^=getsgo(x);
		}
	}
	else {
		for(int i=1;i<=n;i++) {
			scanf("%d",&x);
			tmp^=getsge(x);
		}
	}
	printf(tmp?"Kevin":"Nicky");
}