生成函数浅入

还没学，但是记一下学长说的式子。
给定k,p，$1\le k\le 10^9$，$0<p<1$，求${\sum }_{i\ge 0}{(}_k^i)p^i$
$$\begin{gathered} {\sum }_{i\ge 0}{(}_k^i)p^i \\ ={\sum }_{i\ge 0}{C}_i^k{p}^i \\ ={\sum }_{i\ge 0}[x^k](x+1{)}^i{p}^i \\ =[x^k]{\sum }_{i\ge 0}(x+1{)}^i{p}^i \end{gathered}$$

设$S={\sum }_{i\ge 0}(x+1{)}^i{p}^i$
设$t=(x+1)p$
根据等比数列求和公式有
$S={\sum }_{i\ge 0}{t}^i=\frac{1-t^{\infty }}{1-t}=\frac{1}{1-t}=\frac{1}{-px-p+1}$
将$-px+(1-p)$作为除数，1作为被除数，1为最高项进行多项式除法。
接着你会发现从右到左依次是$\frac{1}{1-p}，\frac{p}{(1-p{)}^2}，\frac{p^2}{(1-p{)}^3}...$
其实这就是S的第0、1、2…项。
设$S_i=[x^i]S$，那么$S_0=\frac{1}{1-p}$
$S_i=\frac{p}{1-p}{S}_{i-1}(i\ge 1)$
那么有通项$S_i=(\frac{p}{1-p}{)}^i{S}_0$
那么原式$=[x^k]{\sum }_{i\ge 0}(x+1{)}^i{p}^i=S_k=(\frac{p}{1-p}{)}^k{S}_0$
这个直接快速幂求就可以了。

注意到分母为1-p，这也是为什么规定0<p<1的原因。