洛谷P2490 [SDOI2011] 黑白棋题解

题目链接：P2490 [SDOI2011] 黑白棋

题意：

小 A 和小 B 又想到了一个新的游戏。

这个游戏是在一个 \(1 \times n\) 的棋盘上进行的，棋盘上有 \(k\) 个棋子，一半是黑色，一半是白色。

最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。

小 A 可以移动白色棋子，小 B 可以移动黑色的棋子，其中白色不能往左，黑色不能往右。他们每次操作可以移动 \(1\) 到 \(d\) 个棋子。

每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。

小 A 和小 B 轮流操作，现在小 A 先移动，有多少种初始棋子的布局会使他胜利呢？

输入格式：

输入三个数 \(n,k,d\)。

输出格式：

输出小 A 胜利的方案总数。答案对 \(10^9+7\) 取模。

数据范围：

保证 \(1 \leq d \leq k \leq n \leq 10^4\)，\(k\) 为偶数，\(k \leq 100\)。

由于终止状态一定是 “……黑白…黑白…黑白……” 的情况

所以我们可以把相邻两个黑白棋子的距离看作一堆石子，那么问题就转化为了一个 K–Nim 游戏

确切的讲，是一个 \(d\)–Nim游戏，因为每次可以操作不超过 \(d\) 堆石子。

记 \(b_s = \sum_{i=1}^n\left(a_i\right)_s\) ，其中 \((x)_s\) 表示 \(x\) 二进制下第 \(s\) 位。

因为 \(d\)–Nim 先手必胜的条件是存在一个 \(s\) 满足 \(b_s\not\equiv 0 \pmod{d+1}\) ，所以问题转化为找这样的情况数。

正难则反。考虑设 \(f(i,j)\) 表示前 \(i\) 位（记 \(0\) 到 \(i-1\) 位）中 \(b_j\equiv 0 \pmod{d+1}\) 。

转移考虑枚举第 \(i\) 位中选出 \(x(d+1)\) 堆为 \(1\) 的，有 \[ f(i+1,\,j+2^i\cdot x(d+1)) \operatorname{\big\uparrow} \binom{\frac{k}{2}}{x(d+1)}f(i,j) \] 这里 \(\uparrow\) 表示 a += b 。记 \(c~(c \ge 0)\) 为最高位，那么答案就是 \[ \binom{n}{k} - \sum_{i=1}^{n-k} \binom{n-i-\frac{k}{2}}{\frac{k}{2}}f(c + 1,\,i) \] 时间复杂度 \(\mathcal{O}(n \log n \log_d n)\) ，可能还有更紧的上界不过已经足够小了。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
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)(1e4 + 15))

int dp[15][N], C[N][233];
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, k, d; cin >> n >> k >> d;
    rep(i, 0, n) C[i][0] = 1;
    rep(i, 1, n) rep(j, 1, min(i, k)) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    dp[0][0] = 1;
    rep(i, 0, 12) rep(j, 0, n - k)
    {
        const int now = 1ll << i;
        for(int x = 0; j + now * x * (d + 1) <= n - k && x * (d + 1) <= k / 2; x++)
            add(dp[i + 1][j + now * x * (d + 1)], dp[i][j] * C[k / 2][x * (d + 1)] % mod);
    }
    int res = 0;
    rep(i, 0, n - k) add(res, dp[13][i] * C[n - i - k / 2][k / 2] % mod);
    cout << (C[n][k] + mod - res) % mod << '\n';
    return 0;
}