[HNOI2007]分裂游戏

博弈论

题面

有$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<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#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;
}