HDU 6397 (MultiSchool Round8 Problem 1001)

未分类

---

题意：
$m$个盒子，每个盒子里面有完全一样的$n-1$个球，从每个盒子里面取球（可能取出$0,1,...,n-2,n-1$个），问恰好总共取出$k$个球的方案数有多少种？两个方案数不同当且仅当在某个盒子里面取的个数不一样.答案对$998244353$取模.
数据范围$(1\leq n,m\leq 10^5,0\leq k \leq 10^5$).

解析：
先尝试构造这个玩意的母函数：$f(x)=(1+x^1+x^2+...+x^{n-1})^m$，要求的答案就是$x^k$的系数.
先用等比数列求和公式化简一下：

$$\begin{align*} f(x) &=(\frac{1-x^n}{1-x})^m \\ &= (1-x^n)^m (\frac{1}{1-x})^m \\ &= (1-x^n)^m (1+x+x^2+...+x^n+...)^m \\ \end{align*}$$
容易知道左边的式子的$x$的幂为$ni$的时候才会有系数不为$0$,那么枚举左边的幂为$ni$，那么右边的式子只有$x^{k-ni}$的系数会对答案有贡献，那么现在要求左边式子$x^{ni}$的系数和右边式子的$x^{k-ni}$的系数.
直接说结论，左边式子$x^{ni}$的系数是$C_m^i(-1)^i$,右边式子的系数是$C_{k-ni+m-1}^{m-1}$.
通过$O(m+k)$预处理阶乘和逆元，可以在$O(n+m+k)$时间处理该问题.