对 \(k=0\sim K\) 求 \(\sum\limits_{i=0}^{\infty}p^i\dbinom{i}{k}\)。
\[\begin{aligned} &\sum_{i=0}^{\infty}p^i\binom{i}{k}\\ =&\sum_{i=0}^{\infty}p^i[x^k](1+x)^i\\ =&[x^k]\sum_{i=0}^{\infty}(p(1+x))^i\\ =&[x^k]\dfrac{1}{1-p-px} \end{aligned} \]于是可以 \(O(K\log K)\) 求了。
哦不好意思上面都是在瞎扯（
实际上：
\[\begin{aligned} &\sum_{i=0}^{\infty}p^i\binom{i}{k}\\ =&\dfrac{1}{k!}\sum_{i=k}^{\infty}p^i i^{\underline{k}} \end{aligned} \]注意到：
\[\begin{aligned} \left(\dfrac{1}{1-x}\right)^{(k)}=\left(\sum_{i=0}^{\infty}x^i\right)^{(k)}=\sum_{i=k}^{\infty}i^{\underline{k}}x^{i-k} \end{aligned} \]而由数学归纳法可知：
\[\left(\dfrac{1}{1-x}\right)^{(k)}=\dfrac{k!}{(1-x)^{k+1}} \]那么 \(x^k\dfrac{k!}{(1-x)^{k+1}}=\sum\limits_{i=k}^{\infty}i^{\underline{k}}x^{i}\)。
于是：
\[\begin{aligned} &\sum_{i=0}^{\infty}p^i\binom{i}{k}\\ =&\dfrac{1}{k!}\sum_{i=k}^{\infty}p^i i^{\underline{k}}\\ =&\dfrac{1}{k!}p^k\dfrac{k!}{(1-p)^{k+1}} \end{aligned} \]于是 \(O(K)\) 预处理好阶乘之后单个 \(p,k\) 就可以 \(O(1)\) 求了。
对 \(k=0\sim K\) 求 \(\sum\limits_{i=0}^{\infty}p^ii^k\)。
\[\begin{aligned} &\sum_{i=0}^{\infty}p^i i^k\\ =&\sum_{i=0}^{\infty}p^ik![x^k]e^{ix}\\ =&k![x^k]\sum_{i=0}^{\infty}(pe^x)^i\\ =&k![x^k]\frac{1}{1-pe^x} \end{aligned} \]于是可以 \(O(K\log K)\) 求了。
事实上你也可以用第二类斯特林数展开 \(i^k\)，然后套用第一个问题的公式得到：
\[\sum_{i=0}^{\infty}p^ii^k=\sum_{l=0}^{k}\begin{Bmatrix}k\\l\end{Bmatrix}p^{l}\dfrac{l!}{(1-p)^{l+1}} \]这样单个 \(p,k\) 是 \(O(K)\) 的，如果要求多个 \(k\) 的话就是 \(O(K^2)\) 的了。
所以说这次 \(O(K\log K)\) 是正经的。
标签：infty,begin,end,函数,求和,dfrac,sum,无限,aligned From： https://www.cnblogs.com/ez-lcw/p/16843074.html