为了解决 EA 的时间复杂度问题把这道题搞懂了（
翻棋子游戏有一个我不会证的套路：分别独立考虑每一个可操作的棋子，看做独立的游戏，将 SG 函数值异或起来。
则若只有 \(x\) 为白，后继状态的 SG 函数值的集合应为 \(\newcommand\SG{\mathrm{SG}}\{0,\SG(2x),\SG(2x) \oplus \SG(3x),\ldots,\SG(2x) \oplus \cdots \SG(\left\lfloor\frac nx\right\rfloor x)\}\)。
那么又有一个结论：\(\left\lfloor\frac nx\right\rfloor\) 值相等的 \(x\) 的 SG 函数值也相等。
证明可以考虑从大到小归纳，此处不展开。
则考虑数论分块，只需要计算 \(O(\sqrt n)\) 个位置的 SG 函数值。
为了计算 SG 函数值，还需要枚举后继状态转移。
注意到可以再次数论分块。
总复杂度为 \(O(n^{3/4})\)。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
const int N = 1e9;
const int MX = 32e3;
int n,lim,k;
int le[MX + 5],ge[MX + 5];
int lis[2 * MX + 5],tot;
int vis[2 * MX + 5];
inline int &id(int x)
{
return x <= lim ? le[x] : ge[n / x];
}
int sg[2 * MX + 5],ans;
int main()
{
scanf("%d",&n),lim = sqrt(n);
for(register int l = 1,r;l <= n;l = r + 1)
{
r = n / (n / l);
lis[id(n / l) = ++tot] = n / l;
}
for(register int i = 1,x;i <= tot;++i)
{
vis[x = 0] = i;
for(register int L = 2,R;L <= n / lis[i];L = R + 1)
{
R = n / lis[i] / (n / lis[i] / L);
vis[x ^ sg[id(R * lis[i])]] = i,!(R - L & 1) && (x ^= sg[id(R * lis[i])]);
}
for(x = 0;vis[x] == i;++x);
sg[i] = x;
}
scanf("%d",&k);
for(int w,a;k;--k)
{
ans = 0;
for(scanf("%d",&w);w;--w)
scanf("%d",&a),ans ^= sg[id(a)];
puts(ans ? "Yes" : "No");
}
}