题意
把 $n$ 个颜色不同的球放入 $m$ 个相同的盒子里，且不存在一个盒子里装着超过 $k$ 个球。求方案数对 $998244353$ 取模。
两个方案不同，仅当存在对应盒子，使得第一个方案中的盒子中有一个 第二个方案的盒子中没有的 颜色的球。
$T$ 组数据。
$1 \leq T \leq 200, 1 \leq m, k \leq n \leq 10^6，\sum n \leq 10^8$，时限 3 秒。
题解
长得很像生成函数。考虑一个盒子的生成函数：$\displaystyle\sum\limits_{i = 1}^k x^i$。总共 $m$ 个盒子的方案数就是 $\left(\displaystyle\sum\limits_{i = 1}^k x^i\right)^m$ 的 $n$ 次项系数。
而因为球不同，所以要乘上 $n!$，而因为盒子相同，所以要除以 $m!$。
$$\frac{n!}{m!} \cdot \left[x^n\right]\left(\sum\limits_{i = 1}^k x^i\right)^m$$
这个不太好算，但是可以推出 $\displaystyle\sum\limits_{i = 1}^k x^i$ 的封闭形式为：$x \dfrac{1 - x^k}{1 - x}$。
所以现在的答案就是
$$ \begin{aligned} A\left(x\right) &= \frac{n!}{m!} \cdot \left[x^n\right]\left(x \frac{1 - x^k}{1 - x}\right)^m \\ &=\frac{n!}{m!} \cdot \left[x^n\right]x^m\frac{\left(1 - x^k\right)^m}{\left(1 - x\right)^m} \\ &=\frac{n!}{m!} \cdot \left[x^{n - m}\right]\frac{\left(1 - x^k\right)^m}{\left(1 - x\right)^m} \end{aligned} $$
而
$$ \left(1 - x^k\right)^m = \sum \limits_{i = 0}^m\binom mi \left(-1\right)^ix^{ik}\\ \left(1 - x\right)^{-m} = \sum \limits_{i = 0}^\infin\binom {m - 1 + i}{m - 1} x^i $$
上式可以暴力算，只需要求下式的 $n - m - ik$ 项系数即可。
还有一个容斥的做法，可以看这里
代码
void solve() {
tp n, m, k; bin >> n >> m >> k;
Mod_Int ans = 0;
for (tp i = 0; i <= m; ++i) {
tp t = n - i * k - 1;
if (t < m - 1) break;
ans += comb.binom(t, m - 1) * comb.binom(m, i) * (i % 2 ? -1 : 1);
}
bin << ans * comb.fac(n) * comb.invfac(m) << '\n';
}