题面

有\(n\)堆石子，每次可取第\(i\)堆石子的一颗，然后再各在\(j,k\)堆石子中放一颗（\(i<j\leq k\))。无法操作者输。问先者是否有必胜策略，和在胜利前提下，第一步有多少种取法。

• \(n\leq21,a_i\leq10000\)

解析

显然游戏结束的条件是只有最后一堆有石子。

若先者要赢，首先应把各堆石子全部变为偶数，这样只用模仿对手操作即可胜利。

于是记忆化搜索计算每堆石子的\(SG\)值（后继状态是第\(j\)堆和第k$堆石子）。

注意到目的，我们只统计\(a_i\&1==1\)的\(SG\)值异或和，得到\(ans\)。

然后可以枚举取的是哪堆石子，若取完后能使当前局面异或和清\(0\)（即\(ans\bigoplus SG[i]\bigoplus SG[j]\bigoplus SG[k]==0\)），就是合法方案的一种。

注意一下判\(vis\)的小技巧。

// luogu-judger-enable-o2#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define re register#define il inline#define fp(i,a,b) for(re int i=a;i<=b;i++)#define fq(i,a,b) for(re int i=a;i>=b;i--)using namespace std;const int N=50;int n,a[N],SG[N],vis[N],ans,tot;il ll gi(){ re ll x=0,t=1; re char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*t;}il int dfs(re int x){ if(SG[x]!=-1) return SG[x]; fp(i,x+1,n) fp(j,i,n) vis[dfs(i)^dfs(j)]=x; re int p=0; while(vis[p]==x) ++p; return SG[x]=p;}int main(){ re int T=gi(); while(T--) { memset(SG,-1,sizeof(SG));memset(vis,0,sizeof(vis));ans=0;tot=0; n=gi(); fp(i,1,n) a[i]=gi(); fp(i,1,n) if(a[i]&1) dfs(i); fp(i,1,n) if(a[i]&1) ans^=dfs(i); fp(i,1,n) fp(j,i+1,n) fp(k,j,n) if((ans^dfs(i)^dfs(j)^dfs(k))==0) { if(!tot) printf("%d %d %d\n",i-1,j-1,k-1); ++tot; } if(!tot) puts("-1 -1 -1"); printf("%d\n",tot); } return 0;}