给n个位置， 每个位置有一个小球。 现在两个人进行操作， 每次操作可以选择一个位置i， 拿走一个小球。然后在位置j, k(i<j<=k)处放置一个小球。 问你先进行什么操作会先手必胜以及方法数量。

 

感觉这题好神

如果一个位置有偶数个小球， 那么等价于这个位置没有小球。 因为第二个人可以进行和第一个人相同的操作。 所以初始值%2。

然后我们把每个位置看成一个状态， 如果i有一个小球， 等价于j, k 也有一个小球。 然后转移。

方法数量就n^3枚举就可以了。

#include 
     
      using namespace std;#define mem1(a) memset(a, -1, sizeof(a))int sg[22], a[22], n;int mex(int x){    if(~sg[x])        return sg[x];    bool vis[1000];    memset(vis, 0, sizeof(vis));    for(int i = x + 1; i <= n; i++) {        for(int j = i; j <= n; j++) {            vis[mex(i)^mex(j)] = 1;        }    }    for(int i = 0; ; i++) {        if(!vis[i])            return sg[x] = i;    }}int main(){    int t;    cin>>t;    while(t--) {        cin>>n;        for(int i = 1; i <= n; i++) {            scanf("%d", &a[i]);        }        mem1(sg);        int ans = 0, cnt = 0;        for(int i = 1; i <= n; i++) {            if(a[i]&1) {                ans ^= mex(i);            }        }        int flag = 0;        for(int i = 1; i <= n; i++) {            for(int j = i + 1; j <= n; j++) {                for(int k = j; k <= n; k++) {                    ans ^= mex(i)^mex(j)^mex(k);                    if(!flag && ans == 0) {                        printf("%d %d %d\n", i-1, j-1, k-1);                        flag = 1;                    }                    if(ans == 0) {                        cnt++;                    }                    ans ^= mex(i)^mex(j)^mex(k);                }            }        }        if(cnt != 0)            cout<
      
       <