2022 年牛客多校第十场 G 题题解

G Steins’ Game 2

题意：有 $nn$ 堆石子 $\{a_n\}\backslash \{a\_n\backslash \}$，满足 $0\le a_1\le a_2\cdots \le a_n\le m0\; \backslash leq\; a\_1\; \backslash leq\; a\_2\backslash cdots\; \backslash leq\; a\_n\; \backslash leq\; m$。Alice 与 Bob 依次从非空的一堆拿走正数个石子使得每堆石子的石子个数仍然是非递减的。求有多少种合法的石子分配方案使得 Bob 必胜。$n\le 4\times 10^{4}n\backslash leq\; 4\backslash times\; 10^4$，$m\le 1\times 10^{12}m\; \backslash leq\; 1\backslash times\; 10^\{12\}$。

解法：考虑 $\{a_n\}\backslash \{a\_n\backslash \}$ 的差分数组 $\{b_n\}\backslash \{b\_n\backslash \}$，则该问题与 $\{b_n\}\backslash \{b\_n\backslash \}$ 序列构成的阶梯 Nim（有 $nn$ 堆石子，每次可以从第 $ii$ 堆的石子中拿走一部分放到第 $i-1i-1$ 堆中，或者把第 $11$ 堆中的石子拿走一部分，无法操作者算输）是完全等价的。考虑 Bob 获胜条件，利用阶梯 Nim 的必胜条件：奇数堆石子的异或值为 $00$。得到这题的转化题意：前 $k=\lceil {\displaystyle \frac{n}{2}}\rceil k=\backslash left\; \backslash lceil\; \backslash dfrac\{n\}\{2\}\backslash right\; \backslash rceil$ 个石子异或值为 $00$，$\sum b_i=m\backslash sum\; b\_i=m$ 的方案数。这是因为如果有奇数堆石子，则最后新添加一堆石子不会影响阶梯 Nim 的性质，这时不妨在 $\{a_n\}\backslash \{a\_n\backslash \}$ 的末尾添加一堆石子数为 $mm$ 的石子；若原来有偶数堆石子，也可以在 $\{a_n\}\backslash \{a\_n\backslash \}$ 的最后增补两堆均为 $mm$ 的石子，此时对于 $\{b_n\}\backslash \{b\_n\backslash \}$ 序列只是增加了一个 $00$。则该转化将 $\{b_n\}\backslash \{b\_n\backslash \}$ 中奇数堆石子移动到最前面，变成前缀异或和，且忽略了 $\{b_n\}\backslash \{b\_n\backslash \}$ 中每个数字的大小关系。

考虑每一个数字的每一个 bit 位上填 $0,10,1$ 的方案。对于 $2^{k}2^k$ 这一 bit，要求前缀 $kk$ 的异或和为 $00$ 的的生成函数为 $f(x)={\displaystyle \sum _{i=0}^k[i\mathrm{m}\mathrm{o}\mathrm{d}2=0]\left(\genfrac{}{}{0px}{}{k}{i}\right)x^i}f(x)=\backslash displaystyle\; \backslash sum\_\{i=0\}^\{k\}[i\; \backslash bmod\; 2=0]\{k\; \backslash choose\; i\}x^i$，即仅能选择偶数个数字填 $11$，并且进行选择。对于剩余的 $n-kn-k$ 个数字，可以任选，其方案为 $g(x)=(1+x{)}^{n-k}g(x)=(1+x)^\{n-k\}$，因而整层的填法方案的生成函数为 $h(x)=f(x)g(x)h(x)=f(x)g(x)$。不难发现，对于每一层的填法均相同，因而可以预处理。

接下来考虑背包的容量。这一处理与 2022 年牛客第一场的 H 题是完全一样的：$f_{i,j}f\_\{i,j\}$ 表示填完低 $ii$ 个 bit，最后剩余 $j{2}^{i}j2^i$ 的容量的方案数。则转移是显然的：${\displaystyle f_{i+1,j}=\sum _{k=0}^l{f}_{i,k}[x^{l-k}]h(x)}\backslash displaystyle\; f\_\{i+1,j\}=\backslash sum\_\{k=0\}^\{l\}\; f\_\{i,k\}[x^\{l-k\}]h(x)$，其中 $l=2j+{\mathrm{b}\mathrm{i}\mathrm{t}}_{i}l=2j+\{\backslash rm\; bit\}\_i$ 表示当前位的最大容量。注意到这个 $j\le 2nj\; \backslash leq\; 2n$（更大了则完全填不上），因而只需要保留 $2n2n$ 项即可。

总时间复杂度 $\mathcal{O}(n\log n\log m)\backslash mathcal\; O(n\; \backslash log\; n\; \backslash log\; m)$。

int main()
{
    int n;
    long long m;
    scanf("%d%lld", &n, &m);
    Poly a, b;
    if (n % 2 == 0)
    {
        int k = n / 2 + 1;
        b.resize(k + 1);
        a.resize(n / 2 + 1);
        for (int i = 0; i <= k; i++)
            b[i] = C(k, i);
        for (int i = 0; i <= n / 2; i += 2)
            a[i] = C(n / 2, i);
    }
    else
    {
        int k = (n + 1) / 2;
        b.resize(k + 1), a.resize(k + 1);
        for (int i = 0; i <= k; i++)
            b[i] = C(k, i);
        for (int i = 0; i <= k; i += 2)
            if (i % 2 == 0)
                a[i] = C(k, i);
    }
    auto way = a * b;
    vector<int> digit;
    long long x = m;
    while (x)
    {
        digit.push_back(x & 1);
        x >>= 1;
    }
    f[0][0] = 1;
    for (int k = 1; k <= digit.size(); k++)
    {
        Poly cur(2 * n + 5);
        for (int i = 0; i <= n + 1;i++)
            cur[i] = f[k - 1][i];
        cur = cur * way;
        for (int i = 0; i <= n + 1;i++)
            f[k][i] = cur[i * 2 + digit[k - 1]];
    }
    printf("%lld", f[digit.size()][0]);
    return 0;
}