洛谷P5363 [SDOI2019] 移动金币题解

题目链接：P5363 [SDOI2019] 移动金币

题意：

Alice 和 Bob 将要进行如下的一场游戏。二人轮流操作，且 Alice 先行。

当轮到一个玩家的时候，他可以选择一枚金币，并将其向左移动任意多格，且至少移动一格。金币不能被移出棋盘，也不能越过其它金币。

一个 $1\times n$ 的棋盘上最初摆放有 $m$ 枚金币。其中每一枚金币占据了一个独立的格子，任意一个格子内最多只有一枚金币。

如果轮到一个玩家的时候他已经无法做出任何有效操作了（显然这个时候 $m$ 枚金币恰好落在最左侧的 $m$ 个格子中），则被判定为输家。已经知道 Alice 和 Bob 都是极致聪明的人，他们在任何局面下总能做出最优的操作。那么有多少初始状态能保证 Alice 必胜呢？

输入格式：

输入仅有一行并包含两个正整数，依次为 $n$ 和 $m$，如题目所述。

输出格式：

输出一个整数，表示有多少初始状态可以保证 Alice 作为先手方能先手必胜。

由于答案可能很大，请输出关于 $10^9+9$ 取模后的值。

数据范围：

$1\le n\le 1.5\times 10^5$ 且 $1\le m\le 50$。

考虑如何判断一个状态是否为先手必胜态 $\rm N$ 。

记 $x_i$ 为每个棋子的位置，并记 $b_i = x_i - x_{i-1}-1$ 为每个棋子初始可以移动的格数。

注意到当第 $i$ 个金币移动 $x$ 格时，会使得 $b_i \gets b_i - x$ 且 $b_{i + 1} \gets b_{i + 1} + x$ 。

于是这就变成了一个反着的阶梯博弈，也就是从 $m + 1$ 开始的阶梯博弈，参考 P3480 题解。

阶梯博弈的结论是，先手为 $\rm N/P$ 取决与奇数堆的 Nim 游戏是什么。

本题因为是反过来的，所以先手为必败态 $\rm P$ 当且仅当 $n,\,n-2,\,\cdots$ 这些位置满足异或和为 $0$ 。

如果求出有多少个状态为 $\rm P$ ，那么用总数减去 $\rm P$ 的状态数就是答案了。

现在问题就变成了将 $n$ 个格子放进 $m+1$ 个盒子里，盒子可空，且与 $m + 1$ 奇偶性相同的盒子异或和为 $0$ 。

这个异或和不太好直接搞，套路地考虑枚举二进制下每一位 $2^i$ ，每次我们会放偶数个这样的位。

考虑设 $f(i,j)$ 为考虑前 $i$ 位（从低到高），还剩 $j$ 个格子没放到盒子里时状态为 $\rm P$ 的方案数。那么

$f(i,j) = \sum_{k\ \mathrm{is\ even}} \binom{\left\lfloor\frac{m+1}{2}\right\rfloor}{k}f(i + 1,j - k\cdot 2^i)$

其中 $\left\lfloor\frac{m+1}{2}\right\rfloor$ 是盒子的个数。

这样子还可能有剩余的格子没有塞到盒子里。考虑插板法塞到与 $m+1$ 奇偶性不同的位置，那么

$\mathrm{Ans} = \binom{n}{m} - \sum_{i=0}^{n - m}\binom{i + \left\lfloor\frac{m+1}{2}\right\rfloor - 1}{\left\lfloor\frac{m+1}{2}\right\rfloor -1}f(i,0)$

时间复杂度 $\mathcal{O}(nm \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 9;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))

int res, lg[N], fac[N], infac[N], f[21][N];
int qpow(int a, int b)
{
    int r = 1;
    for(a %= mod; b; b >>= 1, a = a * a % mod)
        if(b & 1) r = r * a % mod;
    return r;
}
int C(int n, int m)
{
    if(n < m || m < 0) return 0;
    return fac[n] * infac[n - m] % mod * infac[m] % mod;
}
void init(int n)
{
    fac[0] = 1;
    rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
    infac[n] = qpow(fac[n], mod - 2);
    Rep(i, n - 1, 0) infac[i] = infac[i + 1] * (i + 1) % mod;
    rep(i, 2, n) lg[i] = lg[i >> 1] + 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m; if(n < m) return cout << "0\n", 0;
    init(n + m + 5); ; f[lg[n] + 1][n - m] = 1;
    Rep(i, lg[n], 0) rep(j, 0, n - m) if(f[i + 1][j])
        for(int k = 0; k <= (m + 1) / 2 && k * (1ll << i) <= j; k += 2)
            add(f[i][j - k * (1ll << i)], f[i + 1][j] * C((m + 1) / 2, k) % mod);
    rep(i, 0, n - m) add(res, f[0][i] * C(i + (m + 2) / 2 - 1, (m + 2) / 2 - 1) % mod);
    cout << (C(n, m) + mod - res) % mod << '\n';
    return 0;
}