题目链接：ARC 102C

Takahashi 有 $n$ 个骰子，每个骰子有 $k$ 个面分别标号为 $1$ 到 $k$。对于每个 $i = 2, 3, \dots, 2k$，求满足以下条件的方案数对 $998244353$ 的值。

• 投掷这 $n$ 个骰子，没有任何两个不同骰子的数字之和为 $i$。

注意骰子之间是相同的。也就是说，当存在整数 $k$ 使得两个方案数数字 $k$ 的骰子数量不同，那么这两个方案被认为是不同的。

数据范围：$2 \le n \le 2000$，$1 \le k \le 2000$。

Solution

由于数据范围只有 $2000$，我们考虑容斥。

对于确定的 $i = 2, 3, \cdots, 2k$，我们枚举有至少 $j$ 对不满足条件的骰子。假如构成 $x$ 的无序数字对数量为 $tot$，那么这 $k$ 对骰子有 $\binom{tot}{j}$ 种方案数。

接下来考虑剩下的 $n - 2j$ 个骰子。问题转化为：有 $k$ 种数字，第 $i$ 种数字有 $a_i$ 个，这 $k$ 种数字一共有 $n - 2j$ 个。这个问题是平凡的，利用隔板法可以得到方案数 $\binom{n - 2j + k - 1}{k - 1}$。

故我们利用容斥得到答案：

$$ \sum_{j = 0} ^ {\min(tot, \left\lfloor\frac{n}{2}\right\rfloor)} (-1) ^ j\binom{tot}{j}\binom{n - 2j + k - 1}{k - 1} $$

时间复杂度：$\mathcal O(nk)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 4e3 + 5;
const int P = 998244353;

int n, k, c[N][N];

void init(int n) {
    c[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
        }
    }
}
void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
int main() {
    scanf("%d%d", &k, &n);
    init(n + k);
    for (int i = 2; i <= k + k; i++) {
        int cnt = 0, ans = 0;
        for (int j = 1; i - j >= j; j++) {
            cnt += (j <= k && i - j <= k);
        }
        for (int j = 0, sgn = 1; j <= cnt && j + j <= n; j++, sgn = P - sgn) {
            add(ans, 1LL * sgn * c[cnt][j] % P * c[n - 2 * j + k - 1][k - 1] % P);
        }
        printf("%d\n", ans);
    }
    return 0;
}