codeforces 603C. Lieges of Legendre sg函数

时间:2021-10-05 14:14:02

题目链接

n堆石子, 可以拿走一堆中的一颗, 或者将一堆数量为2*x的石子分为k堆x个的石子。k由题目给出。

k分奇偶讨论。 k为偶数时,k堆x个的石子异或结果为0; k为奇数时, k堆x个石子异或结果与mex(x)相等, 然后打不同的sg表找规律, 打表程序看代码。

 #include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ull unsigned long long
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
int sg[];
/*int mex1(int x) {
if(~sg[x])
return sg[x];
int vis[105];
mem(vis);
vis[mex1(x-1)] = 1;
if(x%2==0) //k为奇数
vis[mex1(x/2)] = 1;
for(int i = 0; ; i++)
if(!vis[i])
return sg[x] = i;
}
int mex2(int x) { //k为偶数
if(~sg[x])
return sg[x];
int vis[105];
mem(vis);
vis[mex2(x-1)] = 1;
if(x%2==0)
vis[0] = 1;
for(int i = 0; ; i++)
if(!vis[i])
return sg[i] = i;
}*/
int mex2(int x) {
if(x<=) {
return x;
}
if(x&)
return ;
return ;
}
int mex1(int x) {
if(x<=) {
if(x&)
return ;
if(x==)
return ;
return ;
}
if(x&)
return ;
int tmp = mex1(x/);
if(tmp==)
return ;
return ;
}
int main()
{
mem1(sg);
/*sg[0] = 0;
for(int i = 0; i<=100; i++)
sg[i] = mex1(i);
for(int i = 0; i<=100; i++) {
printf("[%d:%d]\n", i, sg[i]);
}*/
int n, k, x, ans = ;
cin>>n>>k;
while(n--) {
scanf("%d", &x);
if(k&)
ans ^= mex1(x);
else
ans ^= mex2(x);
}
if(!ans) {
puts("Nicky");
} else {
puts("Kevin");
}
return ;
}