题解 P6620 【[省选联考 2020 A 卷] 组合数问题】

这里给出一种由组合意义得出的$O(m\log m)$的做法（需要保证$p$是$998244353$）。 将$f(x)$展开 $$ \begin{aligned} \sum_{k=0}^nf(k)x^k{n\choose k}&= \sum_{k=0}^n\sum_{i=0}^ma_ik^ix^k{n\choose k}\\ &=\sum_{i=0}^ma_i\sum_{k=0}^nk^ix^k{n\choose k} \end{aligned} $$ 考虑第二个$\sum$的组合意义：有$n$个不同的盒子，先从这些盒子中选出$k$个盒子，然后给这$k$个盒子染上$x$种颜色，最后将$i$个有标号的球放入$k$个盒子中。 那么对于一个盒子来说，有三种情况：没有被选中；选中并且染色了，但是没有放入任何球；选中并且染色了，并且放入了若干个球。 写出一个盒子的$EGF$ $$ \begin{aligned} F(t)&=1+x+x\sum_{i\geq 1}\frac{t^i}{i!}\\ &=1+xe^t \end{aligned} $$ 代入原式，可以得到 $$ \begin{aligned} \sum_{i=0}^ma_i\sum_{k=0}^nk^ix^k{n\choose k}&=\sum_{i=0}^ma_i(1+xe^t)^n[t^i]i! \end{aligned} $$ 这里$[t^i]$表示取$t^i$项系数。 最后只需要做一遍$\ln,\exp$即可。