bzoj 4035: [HAOI2015]数组游戏

题意：

有一个长度为$N$的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子，假设它的下标为$x$。接着，选择一个大小在$1$~$\frac n x$之间的整数$k$，然后将下标为$x, 2x \dots kx$的格子都进行颜色翻转。不能操作的人输。现在甲（先手）有一些询问。每次他会给你一个数组的初始状态，你要求出对于这种初始状态他是否有必胜策略。

题解：

如果我们规定不止能选白格子翻，黑格子也可以翻的话，那么这个其实和原游戏是等价的，因为如果一个人翻了黑格子，另一个人肯定可以做同样的操作翻回来。有了这个转化后每个白格子就独立了。只要把每个白格子的$sg$值异或起来就是答案了。$$
sg_i = mex \lbrace XOR_{j=2}^k sg_{i} | k \in [2, \lfloor \frac n i \rfloor]\rbrace

$$
可以发现对于所有$\lfloor \frac n i \rfloor$相等的$i$，它们的$sg$值是一样的。所以就可以用这个来做了。复杂度$O($过得去$)$

#include <bits/stdc++.h>
using namespace std;

int n, T, a[100010], b[100010], m, v[100010], tim = 0, cnt = 0;

int main()
{
    scanf("%d", &n);
    m = sqrt(n);
    for (int i = 1, last; i <= n; i = last + 1)
    {
        last = n / (n / i);
        tim++;
        int now = 0;
        v[0] = tim;
        for (int j = 2, l; j <= last; j = l + 1)
        {
            cnt++;
            l = last / (last / j);
            v[now ^ (last / l < m ? a[last / l] : b[n / (last / l)])] = tim;
            int hh = l - j + 1;
            if (hh & 1) now ^= (last / l < m ? a[last / l] : b[n / (last / l)]);
        }
        int hh = 0;
        while (v[hh] == tim) hh++;
        if (last < m) a[last] = hh;
        else b[n / last] = hh;
    }
    // printf("%d\n", cnt);
    /*
    for (int i = 1, last; i <= n; i = last + 1)
    {
        last = n / (n / i);
        printf("%d %d\n", last, n / last < m ? a[n / last] : b[last]);
    }
    puts("");*/
    scanf("%d", &T);
    while (T--)
    {
        int w, ans = 0;
        scanf("%d", &w);
        for (int i = 0; i < w; i++)
        {
            int x;
            scanf("%d", &x);
            x = n / x;
            ans ^= (x < m ? a[x] : b[n / x]);
        }
        puts(ans ? "Yes" : "No");
    }
}