[HAOI2015]数组游戏

博弈论 分块

题面

有一个长度为$N$的数组，每个格子颜色为黑或白。两人轮流操作。每次操作选择一个白格，假设它的下标为$x$。接着，选择一个大小在$1-n/x$之间的整数$k$，然后将下标为$x$、$2x$、...、$kx$的格子都进行颜色翻转。不能操作的人输。问先手是否有必胜策略。

• $30pts\ n\leq20$
• $50pts\ n\leq10^6$
• $100pts\ n\leq10^9,w\leq100$

解析

$30pts$算法

状态压缩+记忆化搜索

$50pts$算法

该问题很像翻硬币问题。
既然不能翻黑色格子，说明黑色格子的$SG$值对答案没有直接影响。
由性质$SG(A\bigoplus B)=SG(A)\bigoplus SG(B)$，
可知整个游戏的$SG$值为所有可行操作的异或和，即所有白格的$SG$值异或和。

求$SG$值，就是对 所有后继状态（操作后状态）的$SG$值 的异或和取$mex$。
再应用一下上面那个性质，可得一个递推式

模拟一发即可。(看不懂上面可以去蹭蹭我的博弈论总结）
然而我因没注意到存在$SG(x)>x$和一定有$SG(x)>0$而$WA$得怀疑人生。。。
复杂度为$O(nlogn)$。

const int mod=1e9+7,N=1e7+100;
int n,q,w,SG[N],ans,viss[N];
il void getSG(re int x)
{
  re int t=1,tot=0;
  viss[0]=x;
  while(233)
    {
      ++t;
      if(x*t>n) break;
      viss[SG[x*t]^tot]=x;
      tot^=SG[x*t];
    }
  re int tmp=0;while(viss[tmp]==x) ++tmp;
  SG[x]=tmp;
}
int main()
{
  n=gi();q=gi();
  fq(i,n,1) getSG(i);
  while(q--)
  {
      ans=0;
      w=gi();
      fp(i,1,w) ans^=SG[gi()];
      puts(ans?"Yes":"No");
    }
  return 0;
}

$100pts$算法

经过愉快地打$SG$函数表后，发现只要$n/i=n/j$，则$SG(i)=SG(j)$。
于是把$SG$值相同的值合为一块来计算即可。
注意存$SG$值的技巧：分为两半。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#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 mod=1e9+7,N=1e6+100;
int n,q,w,SG[2][N],ans,blk,b[N],id,vis[N];
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 getSG(re int x)
{
  x=n/(n/x);
  if(x<=blk) return SG[0][x];else return SG[1][n/x]; 
}
il void Pre()
{
    for(re int i=1;i<=n;i=n/(n/i)+1) b[++b[0]]=n/(n/i);
    fq(i,b[0],1)
    {
        re int x=b[i],now=0;++id;vis[0]=id;
        for(re int j=x+x;j<=n;)
        {
            re int t=(n/(n/j))/x*x,tmp=(t-j)/x+1;
            vis[now^getSG(j)]=id;
            if(tmp&1) now^=getSG(j);
            j=t+x;
        }
        re int tmp=0;while(vis[tmp]==id) ++tmp;
        if(x<=blk) SG[0][x]=tmp;else SG[1][n/x]=tmp;
    }
}
int main()
{
  n=gi();q=gi();blk=sqrt(n)+1;
  Pre();
  while(q--)
  {
      ans=0;w=gi();
      fp(i,1,w) ans^=getSG(gi());
      puts(ans?"Yes":"No");
    }
  return 0;
}