题解 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即可。