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

2020-06-24 13:59:30


这里给出一种由组合意义得出的$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$即可。