给n个位置， 每个位置有一个小球。 现在两个人进行操作， 每次操作可以选择一个位置i， 拿走一个小球。然后在位置j, k(i<j<=k)处放置一个小球。 问你先进行什么操作会先手必胜以及方法数量。
感觉这题好神
如果一个位置有偶数个小球， 那么等价于这个位置没有小球。 因为第二个人可以进行和第一个人相同的操作。 所以初始值%2。
然后我们把每个位置看成一个状态， 如果i有一个小球， 等价于j, k 也有一个小球。 然后转移。
方法数量就n^3枚举就可以了。
#include <bits/stdc++.h>
using namespace std;
#define mem1(a) memset(a, -1, sizeof(a))int sg[], a[], n;
int mex(int x)
{
if(~sg[x])
return sg[x];
bool vis[];
memset(vis, , sizeof(vis));
for(int i = x + ; i <= n; i++) {
for(int j = i; j <= n; j++) {
vis[mex(i)^mex(j)] = ;
}
}
for(int i = ; ; i++) {
if(!vis[i])
return sg[x] = i;
}
}
int main()
{
int t;
cin>>t;
while(t--) {
cin>>n;
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
}
mem1(sg);
int ans = , cnt = ;
for(int i = ; i <= n; i++) {
if(a[i]&) {
ans ^= mex(i);
}
}
int flag = ;
for(int i = ; i <= n; i++) {
for(int j = i + ; j <= n; j++) {
for(int k = j; k <= n; k++) {
ans ^= mex(i)^mex(j)^mex(k);
if(!flag && ans == ) {
printf("%d %d %d\n", i-, j-, k-);
flag = ;
}
if(ans == ) {
cnt++;
}
ans ^= mex(i)^mex(j)^mex(k);
}
}
}
if(cnt != )
cout<<cnt<<endl;
else {
printf("-1 -1 -1\n0\n");
} }
return ;
}