P2490 [SDOI2011]黑白棋

P2490 [SDOI2011]黑白棋

注意到白棋只能向右，黑棋只能向左，那么一对“黑棋-白棋”（最左侧是白棋，最右侧是黑棋，因此不存在和边界构成一个区间的情况）距离为 $a$ ，可以视作一堆个数为 $a$ 的石子，双方都可以取，同时中间还可以有一些空缺。每次最多选择 $d$ 堆石子，即 $K-Nim$ 游戏，先手必败当且仅当对于所有二进制位的和 $s$ 有 $(d + 1) | s$ 。

考虑 DP $f _ {i, j}$ 表示前 $i$ 位用了 $j$ 个位置满足二进制每一位都是 $d + 1$ 的倍数，每次考虑从 $\frac m 2 $ 堆石子选择出若干堆选择这一位，用组合算。最后统计答案，总方案 $\binom n m$ 减去所有不合法的方案。此时石子个数都已确定，将一对“黑棋-白棋”视作一个整体，还剩下 $n - i - \frac m 2$ 的位置选出 $\frac m 2 $ 个。

查看代码

#include <cstdio>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
typedef long long L;
const int N = 1e4 + 10, M = 14, mod = 1e9 + 7;
void add (int &x, L k) { x = (x + k) % mod; }
int n, m, d, f[M][N];
int inv[N], fact[N], ifact[N];
void init ()
{
    inv[1] = 1;
    for (int i = 2; i < N; ++i)
        inv[i] = (L)(-mod / i) * inv[mod % i] % mod;
    fact[0] = ifact[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        fact[i] = (L)fact[i - 1] * i % mod;
        ifact[i] = (L)ifact[i - 1] * inv[i] % mod;
    }
}
int C (int a, int b) { return a < b ? 0 : (L)fact[a] * ifact[b] % mod * ifact[a - b] % mod; }
int main ()
{
    init();
    read(n, m, d);
    f[0][0] = 1;
    for (int i = 0; i + 1 < M; ++i)
        for (int j = 0; j <= n - m; ++j)
            for (int k = 0; j + (k << i) <= n - m; k += d + 1)
                add(f[i + 1][j + (k << i)], (L)f[i][j] * C(m >> 1, k));
    int res = C(n, m);
    for (int i = 0; i <= n - m; ++i)
        add(res, -(L)f[M - 1][i] * C(n - i - (m >> 1), m >> 1));
    write((res + mod) % mod);
    return 0;
}