求 \(\sum_{i=0}^{\infty}\binom{i}{K}p^i\)，其中 \(\binom{i}{K}=C_i^K\)，\(1\leq K\leq 10^9\)，\(0<p<1\)。
设 \(A(x)\) 为一多项式，\([x^k]A(x)\) 表示这个多项式 \(k\) 次项的系数。
则根据杨辉三角，\(\binom{i}{K}\) 可以表示成 \([x^K](x+1)^i\)，那么原式就可以变化为：
\[\sum_{i=0}^{\infty}\binom{i}{K}p^i=\sum_{i=0}^{\infty}[x^K](x+1)^i p^i=[x^K]\sum_{i=0}^{\infty}(x+1)^i p^i \]令 \(S=\sum_{i=0}^{\infty}(x+1)^i p^i\)，\(t=p(x+1)\)，发现是个等比数列的求和，推一下：（直接套求和公式也可以）
\[\begin{aligned} S&=\sum_{i=0}^{\infty}(x+1)^i p^i=\sum_{i=0}^{\infty}t^i\\ tS&=\sum_{i=1}^{\infty+1}t^i\\ (1-t)S&=t^0-t^{\infty+1}=t^0=1\\ S&=\frac{1}{1-t}=\frac{1}{-px-p+1} \end{aligned}\]设 \(S_i\) 表示 \([x_i]S\)，则有 \(S_i=\dfrac{p}{1-p}S_{i-1}\)，即 \(S_i=\dfrac{p^i}{(1-p)^{i+1}}\)，那我们的答案 \(S_K\) 就可以用快速幂求了。
说一下这个 \(S_i\) 是怎么推的，因为 \(S=\dfrac{1}{1-t}=\dfrac{1}{-px-p+1}\)，所以可以把 \(1\) 看成一个多项式，\(-px-p+1\) 看成一个多项式，然后用大除法求 \(S\) 的每一项系数。
标签：infty,函数,dfrac,sum,生成,多项式,binom,px,遗留 From： https://www.cnblogs.com/ez-lcw/p/16843072.html