Snake (组合数, 容斥)
题意
问将 $n$ 个编号为 $1...n$ 的小球分为 $m$ 个有序组，同时每组中球的数量不超过 $k$ 的方案数。
$1 \le m, k \le n \le 1e6$
思路
首先将所有小球进行全排列，有 $n!$ 种方案。其次考虑到各个组之间的顺序无关，得到 $ \frac{n!}{m!} $ 种方案。
接着进行隔板划分。没有数量超过 $k$ 的组的划分方案不好算，但是可以很容易的计算至少有 $x$ 组中球数至少为 $k$ 的方案数。
先将 $x \cdot k$ 个球取出，然后对剩下的 $n-x \cdot k$ 个球进行隔板划分，方案数为 $C(n-x\cdot k-1, m-1)$。然后将刚刚取出的球选 $x$ 组每组放入 $k$ 个，那么此时就至少有 $x$ 个组有至少 $k$ 个球了，这样的方案数是 $C(m, x)$。
设至少有 $x$ 组中球数至少为 $k$ 的方案数为 $f(x)$。由容斥定理可知，有 $0$ 组球数至少为 $k$ 的方案数为
$$ ans = f(0)-f(1)+f(2)-...-f(2N-1)+f(2N) (N \le m, m \le n-kN) $$Code
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define NL std::cout << '\n'
using lnt = long long;
signed main() {
std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
int t;
std::cin >> t;
const int inf = 0x3f3f3f3f;
const int maxN = 1e6+5;
const int mo = 998244353;
auto ksm = [](lnt x, lnt e) {
lnt ret = 1;
while (e) {
if (e&1) { (ret *= x) %= mo; }
e >>= 1; (x *= x) %= mo;
}
return ret;
};
std::vector<lnt> frac(maxN); frac[0] = 1;
for (int i = 1; i < maxN; ++i) {
(frac[i] = frac[i-1] * i) %= mo;
}
auto C = [&](lnt n, lnt m) {
return frac[n] * ksm(frac[n-m] * frac[m] % mo, mo-2) % mo;
};
while (t--) {
int m, k, n; std::cin >> n >> m >> k;
lnt ret = frac[n] * ksm(frac[m], mo-2) % mo;
lnt tmp = 0;
for (int i = 0; i <= m && n-i*k >= m; ++i) {
if (i&1) {
(tmp -= C(m, i) * C(n-i*k-1, m-1)) %= mo;
} else {
(tmp += C(m, i) * C(n-i*k-1, m-1)) %= mo;
}
}
(ret *= tmp) %= mo;
ret < 0 ? ret += mo : 0;
std::cout << ret; NL;
}
return 0;
}