Team Work
题意：
求 \(\sum_{i=1}^n\dbinom{n}{i}i^k\)
\(n<=1e9,k<=5e3\)
推式子
\[\begin{aligned} 记f_{n,k}&=\sum_{i=1}^n\dbinom{n}{i}i^k \\ &=\sum_{i=1}^n\left[\dbinom{n-1}{i-1}+\dbinom{n-1}{i}\right]i^k \\ &=\sum_{i=1}^n\dbinom{n-1}{i-1}i^k+\sum_{i=1}^{n-1}\dbinom{n-1}{i}i^k \\ &=\sum_{i=1}^n\dfrac{i}{n}\dbinom{n}{i}i^k+f_{n-1,k} \\ &=\dfrac{1}{n}\sum_{i=1}^n\dbinom{n}{i}i^{k+1}+f_{n-1,k} \\ &=\dfrac{1}{n}f_{n,k+1}+f_{n-1,k} \\ 移项得 f_{n,k}&=n(f_{n,k-1}-f_{n-1,k-1}) \end{aligned} \]注意到第二维一直在递减，且最大为 \(5e3\)，且 \(f_{n,0}=\sum_{i=1}^n\dbinom{n}{i}=2^n-1\)，直接递推就做完了，注意当 \(n<k\) 时会出现第二个边界 \(f_{1,k}=1\)。
时间复杂度为 \(O(k^2)\)。
标签：dbinom,报告,dfrac,sum,数学题,aligned,移项 From： https://www.cnblogs.com/07Qyun/p/18462140