题解 P6620 【[省选联考 2020 A 卷] 组合数问题】
An_Account
·
·
题解
这里给出一种由组合意义得出的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即可。