题目概述

有一个长度为 $n$ 的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子，假设它的下标为 $x$ 。接着，选择一个大小在 $1 \sim n$ 之间的整数 $k$，然后将下标为 $x$、$2x$、...、$kx$ 的格子都进行颜色翻转。不能操作的人输。

现在甲（先手）有一些询问。每次他会给你一个数组的初始状态，你要求出对于这种初始状态他是否有必胜策略。

解题报告

我怎么博弈一点都不会啊QAQ，看到这种不可做的奇怪规则就要去想等价规则（然而我根本想不到）。

如果我们允许翻黑格子，并把胜利条件定义为把所有格子翻成黑色，会发现这和原来的规则是一样的！因为翻黑格子之后，不可能立刻获胜，下一轮就可以执行同样的操作翻回来，所以最优解不会去翻黑格子，也就是说和原规则等价。

去掉只能翻白色格子的限制，解法就很显然了，令 $SG(i)$ 表示 $i$ 棋子的SG函数，那么：

$$ SG(i)=mex\{SG(2i)\ xor\ SG(3i)\ xor\cdots xor\ SG(ki)|k\in[2,\lfloor{n\over i}\rfloor\} $$

但是 $n$ 是 $10^9$ ？？？过分了吧？我们观察下性质（打个SG函数表）会发现连续的一片SG函数值是相同的，再想想就发现 $i$ 的SG函数值只与 $\lfloor{n\over i}\rfloor$ 有关，因为决定棋子SG函数值的是该棋子控制棋子的数量。

那么有用的状态就只有 $O(\sqrt n)$ 个了，$O(n)$ 预处理后每次算一下白色棋子SG函数异或值即可。

然而我的写法好像不是很好，带了较大的常数，只能拿 $70$ 分，我就口头AC好了XD。

示例程序

#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=65000;

int n,S,te,ti,vis[maxn+5],sg[2][maxn+5];

#define SG(x) (n/(x)>S?sg[1][x]:sg[0][n/(x)])
inline void Make(){
    for (int l,r=n;r;r=l-1){
            l=n/(n/r+1)+1;int now=0;vis[0]=++ti;
        for (int L=r+1,R;L<=n;L=R+1){
            R=n/(n/L);int tot=R/l-(L-1)/l;
            if (tot&1) now^=SG(L),vis[now]=ti;
            else if (tot>1) vis[now^SG(L)]=ti;
        }
        int f=0;while (vis[f]==ti) f++;
        if (n/l>S) sg[1][l]=f; else sg[0][n/l]=f;
    }
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d",&n);S=sqrt(n);Make();
    for (scanf("%d",&te);te;te--){
        int m,x,ans=0;scanf("%d",&m);
        while (m--) scanf("%d",&x),ans^=SG(x);
        puts(ans?"Yes":"No");
    }
    return 0;
}