题目描述
聪聪和睿睿最近迷上了一款叫做分裂的游戏。
该游戏的规则是： 共有 \(n\) 个瓶子， 标号为 \(0, 1, \ldots, n-1\)，第 \(i\) 个瓶子中装有 \(p_i\) 颗巧克力豆，两个人轮流取豆子，每一轮每人选择 \(3\) 个瓶子，标号为 \(i,j,k\), 并要保证 \(i \lt j, j \leq k\)，且第 \(i\) 个瓶子中至少要有 \(1\) 颗巧克力豆，随后这个人从第 \(i\) 个瓶子中拿走一颗豆子并在 \(j,k\) 中各放入一粒豆子（\(j\) 可能等于 \(k\)） 。如果轮到某人而他无法按规则取豆子，那么他将输掉比赛。胜利者可以拿走所有的巧克力豆！
两人最后决定由聪聪先取豆子，为了能够得到最终的巧克力豆，聪聪自然希望赢得比赛。他思考了一下，发现在有的情况下，先拿的人一定有办法取胜，但是他不知道对于其他情况是否有必胜策略，更不知道第一步该如何取。他决定偷偷请教聪明的你，希望你能告诉他，在给定每个瓶子中的最初豆子数后是否能让自己得到所有巧克力豆，他还希望你告诉他第一步该如何取，并且为了必胜，第一步有多少种取法？
题解
由于此题只和单个巧克力豆有关，于是此题的SG函数是关于豆子本身的。想清楚这点就好做了，令 \(SG(i)\) 代表位置 i 处一颗豆子的SG值，\(n^3\) 枚举转移。
至于输出字典序最小的方案，找第一个使得对方SG值为0的方案即可。
（话说虽然SG值不会很大，但是没有人证枚举的上界啊）
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=30;
int n,sg[N],sum[N],vis[N*100];
signed main(){
for(int i=2;i<=21;i++){
for(int j=i-1;j>=1;j--){
for(int k=j;k>=1;k--){
vis[sg[j]^sg[k]]=i;
}
for(sg[i]=0;vis[sg[i]]==i;sg[i]++);
}
}
int T=rd();
while(T--){
n=rd();
for(int i=1;i<=n;i++)sum[i]=rd()%2;
int ans=0,cnt=0;
for(int i=1;i<n;i++)if(sum[i])ans=ans^sg[n-i+1];
if(ans==0){
printf("-1 -1 -1\n0\n");
continue;
}
int a=-1,b=0,c=0;
for(int i=n;i>=1;i--){
for(int j=i-1;j>=1;j--){
for(int k=j;k>=1;k--){
if((ans^sg[i]^sg[j]^sg[k])==0){
if(a==-1)a=n-i,b=n-j,c=n-k;
cnt++;
}
}
}
}
printf("%d %d %d\n%d\n",a,b,c,cnt);
}
return 0;
}