【题解】江南乐博弈论 luogu3235 ——quhengyi11

传送门喵呜

一道博弈论好题啊！（其实应该说是一道分块好题 (雾

容易想到每次操作答案就是所有子游戏的 nim 和

考虑如何计算 sg 值

$sg[i]$ 表示 $i$ 个石子的 sg 值。

我们有

$sg[i]=mex\{sg[i/j]\oplus \cdots \oplus sg[i/j]\oplus sg[i/j+1] \oplus \dots \oplus sg[i/j+1])|j\in[2,i]\}$

由于它划分的特殊性质 (即划分之后的石子数相差为 1)，我们发现其实只需要看一下 $sg[i/j]$ 和 $sg[i/j+1]$ 的奇偶性就能知道它们对答案的贡献了。

容易知道 $i/j+1$ 的石子数有 $i\%j$ 个， $i/j$ 的石子数有 $j-i\%j$ 个

也就是说我们可以简化 sg 函数的计算方式

$sg[i]=mex\{((j-i\%j) \& 1?sg[i/j]:0)\oplus ((i\%j)\& 1 ? sg[i/j+1] : 0)\}$

注意到对于相同的 $i$ 和 $i/j$ ，总共只有 4 种可能值

然后你就会发现，其实只有两种可能值，你可以证明在上述条件下 $j$ 和 $j+2$ 的奇偶性是一样的

用调整法口胡一下，你相当于将 $i$ 个球均匀丢到 $j$ 个盒子里，现在你变出了两个空盒子，要将球再次均匀分配，你可以在原来的 $j$ 个盒子中拿出两个最多的丢进这两个新盒子，如果最多的只有 1 个了，那就在它的里面拿两个再丢到这两个新盒子里，直到这两个新盒子里的球数是最多的或者次多的为止，容易发现上面的调整过程中最多球的盒子数和次多球的盒子数的奇偶性都没有发生改变

因此我们在 $i$ 和 $i/j$ 相同的所有转移中，只需要求出 $j$ 最小的两个即可

因为 $i/j$ 不同的数的数量是 $\sqrt n$ 级别的，所以总复杂度是 $O(n\sqrt n)$ 的

另外还有一件重要的事情，根据很多题解说你可以不初始化 $mex$ 数组而直接将它赋值为当前的 $x$ 来判别，可是我感觉还是会出问题，因为你在记搜的时候可能会把当前 $mex[i]=x$ 的地方给覆盖掉。那样可能会导致 $sg$ 函数计算错误。我刚开始先计算分 $i+1$ 份然后计算分 $i$ 份的时候会 WA 两个点，~~然而只要把这个顺序倒过来就能 A 了所以我懒得改了~~，所以事实上这样操作 $mex$ 估计是会被 hack 掉的

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 100005
#define M 100005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 100000007
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
int T, F, sg[N], mex[N], n, x, ans;
inline int calc (int x)
{
    if (sg[x] != -1) return sg[x];
    if (x < F) return sg[x] = 0;
    sg[x] = 0;
    for (int i = 2; i <= x; i = x / (x / i) + 1)
    {
        int now = 0;
        int a, b;
        b = x % i; a = i - b;
        if (a & 1) now ^= calc(x / i);
        if (b & 1) now ^= calc(x / i + 1);
        mex[now] = x;
        now = 0;
        if (i != x)
        {
            b = x % (i + 1); a = i + 1 - b;
            if (a & 1) now ^= calc(x / (i + 1));
            if (b & 1) now ^= calc(x / (i + 1) + 1);
            mex[now] = x;
        }
    }
    while (mex[sg[x]] == x) ++sg[x];
    return sg[x];
}
int main ()
{
    scanf("%d %d", &T, &F);
    memset(sg, -1, sizeof sg);
    while (T--)
    {
        ans = 0;
        scanf("%d", &n);
        while (n--)
        {
            scanf("%d", &x);
            ans ^= calc(x);
        }
        printf("%d ", ans ? 1 : 0);
    }
    return 0;
}

update: 今天上课的时候突然发现我那个调整法证明只需要考虑取两个最多球的情况，另一种取的情况会改变盒子里平均分配的球数，是不用讨论的。~~反正就是用更强的结论证明了一个更弱的东西罢了~~

【题解】江南乐博弈论 luogu3235 ——quhengyi11

于2018年12月19日2018年12月19日由HomuraCat发布

HomuraCat

3 条评论

Remmina · 2019年2月8日 11:15 上午

XZYQvQ · 2018年12月19日 11:52 下午

quhengyi11 · 2018年12月20日 12:12 下午

回复 Remmina 取消回复

【题解】江南乐 博弈论 luogu3235 ——quhengyi11

于2018年12月19日2018年12月19日由HomuraCat发布

HomuraCat

3 条评论

Remmina · 2019年2月8日 11:15 上午

XZYQvQ · 2018年12月19日 11:52 下午

quhengyi11 · 2018年12月20日 12:12 下午

回复 Remmina 取消回复

【题解】江南乐博弈论 luogu3235 ——quhengyi11