求 \(\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