博弈论也不会……

To Bouvardia: SG函数打表, 翻棋子模型.

Description

有一个长度为N的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然

后两人轮流进行操作。每次操作选择一个白色的格子，假设它的下标为x。接着，选择一个大小在1~n/x之间的整数

k，然后将下标为x、2x、…、kx的格子都进行颜色翻转。不能操作的人输。现在甲（先手）有一些询问。每次他

会给你一个数组的初始状态，你要求出对于这种初始状态他是否有必胜策略。

Solution

首先这游戏的限制不好满足, 我们转化一步.(没想到)

转化成每个格子都可以选, 把格子全弄黑的人就赢了. 分析一下这个游戏. 假如A选了一个黑格子, 并且转换后对A有利的话, B一定可以把局面还原. 如果选白色格子, 对方还原了这个操作(选黑), 那么自己也同样可以再次还原, 也就是谁选黑色格子都没有意义. 也就是在新游戏中双方还是只会选白格子.

但这时因为随便选, 每个格子就是独立的游戏了. 所以$sg[x] = mex\{sg[x] \oplus sg[2x] \oplus \ldots \oplus sg[kx]\}$.

不过这样跑起来不快.

考场上记得打表可以发现当$n / i$相同时值相同, 可以被数论分块, 所以复杂度就变成$O(N)$了, 而且跳转是不满的, 所以常数小.

大概都是膜题解才打的.

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>

using namespace std;

const int maxp = 105;
const int maxb = 1e+5 + 5;

int n, pri[maxb], bck[maxb], ptr;
int sg[2][maxb];
int bkt[maxb], val[maxb], cnt, blo;

inline int getv(int x) {
  return x > blo ? sg[1][n / x] : sg[0][x];
}
void init() {
  int r;
  for (int i = 1; i <= n; i = r + 1) {
    r = n / (n / i);
    // printf("add %d\n", i);
    pri[++ptr] = i;
    bck[ptr] = r;
  }
  blo = sqrt(n);
  for (int i = ptr; i; --i) {
    int pos = pri[i];
    cnt = 0;
    bkt[0] = 1; val[++cnt] = 0;
    int xorv = 0;
    for (int j = (pos << 1); j <= n; ) {
      int mul = j;
      int fpos = n / (n / j) / pos * pos;
      int num = (fpos - j) / pos + 1;
      if (!num) continue;
      int nval = xorv ^ getv(mul);
      bkt[nval] = 1; val[++cnt] = nval;
      if (num & 1) xorv = nval;
      j = fpos + pos;
    }
    int v = 0;
    while (bkt[v]) ++v;
    if (pos > blo) sg[1][n / pos] = v;
    else sg[0][pos] = v;//, printf("solve %d\n", pos);
    for (int j = 1; j <= cnt; ++j)
      bkt[val[j]] = 0;
  }
}

int main() {
  // freopen("o.out", "w", stdout);
  scanf("%d", &n);
  init();
  int T; scanf("%d", &T);
  /*for (int i = 1; i <= n; ++i)
    printf("%d ", getv(i));
  fclose(stdout);*/
  // puts("");
  while (T--) {
    int m, x, ans = 0; scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
      scanf("%d", &x); ans ^= getv(x);
    }
    puts(ans ? "Yes" : "No");
  }
  return 0;
}