LibreOJ 2126 「HAOI2015」数组游戏

为了解决 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
#include <cstdio>
#include <cmath>
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");
}
}