传送门
鱼 强！
\[ans=\sum\limits_{i=1}^{n}\dbinom{n}{i}
\]
我们有
\[n^m=\sum\limits_{i=0}^{m}\begin{Bmatrix}m\\i\end{Bmatrix}i!\dbinom{n}{i}
\]
得到
\[=\sum\limits_{i=1}^{n}\dbinom{n}{i}\sum\limits_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{i}{j}
\]
\[=\sum\limits_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits_{i=1}^{n}\dbinom{n}{i}\dbinom{i}{j}
\]
\[=\sum\limits_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits_{i=1}^{n}\dbinom{n}{j}\dbinom{n-j}{i-j}
\]
\[=\sum\limits_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{n}{j}\sum\limits_{i=1}^{n}\dbinom{n-j}{i-j}
\]
\[=\sum\limits_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{n}{j}2^{n-j}
\]
此时可以做到\(O(klogk)\)
用通项公式展开\(\begin{Bmatrix}k\\j\end{Bmatrix}\)得到
\[=\sum\limits_{j=0}^{k}\dbinom{n}{j}2^{n-j}\sum\limits_{i=1}^{j}(-1)^i\dbinom{j}{i}(j-i)^k
\]
令第二个求和的\(i\)变为\(j-i\)
\[=\sum\limits_{j=0}^{k}\dbinom{n}{j}2^{n-j}\sum\limits_{i=1}^{j}(-1)^{j-i}\dbinom{j}{i}i^k
\]
\[=\sum\limits_{i=1}^{k}i^k\sum\limits_{j=i}^{k}\dbinom{n}{j}\dbinom{j}{i}2^{n-j}(-1)^{j-i}
\]
\[=\sum\limits_{i=1}^{k}i^k\sum\limits_{j=i}^{k}\dbinom{n}{i}\dbinom{n-i}{j-i}2^{n-j}(-1)^{j-i}
\]
\[=\sum\limits_{i=1}^{k}i^k\dbinom{n}{i}\sum\limits_{j=i}^{k}\dbinom{n-i}{j-i}2^{n-j}(-1)^{j-i}
\]
\[=\sum\limits_{i=1}^{k}i^k\dbinom{n}{i}2^{n-i}\sum\limits_{j=i}^{k}\dbinom{n-i}{j-i}(-\frac{1}{2})^{j}
\]
设\(w=-0.5,f_i\)为后面的和式
容易得到\(f_k=1\)，考虑递推
\[f_i-f_{i+1}
\]
\[=(\sum\limits_{j=0}^{k-i}\dbinom{n-i}{j}w^j)-(\sum\limits_{j=0}^{k-i-1}\dbinom{n-i-1}{j}w^j)
\]
把第一个和式中的\(k-i\)项提出来，其他的并入第二项
\[=\dbinom{n-i}{k-i}w^{k-i}+\sum\limits_{j=0}^{k-i-1}(\dbinom{n-i}{j}-\dbinom{n-i-1}{j})w^j
\]
\[=\dbinom{n-i}{k-i}w^{k-i}+\sum\limits_{j=0}^{k-i-1}(\dbinom{n-i-1}{j-1})w^j
\]
令\(j=j-1\)
\[=\dbinom{n-i}{k-i}w^{k-i}+w\sum\limits_{j=0}^{k-i-2}(\dbinom{n-i-1}{j-1})w^j
\]
\[=\dbinom{n-i}{k-i}w^{k-i}+w(f_{i+1}-\dbinom{n-i-1}{k-i-1}w^{k-i-1})
\]
\[=\dbinom{n-i}{k-i}w^{k-i}+wf_{i+1}-\dbinom{n-i-1}{k-i-1}w^{k-i}
\]
\[=\dbinom{n-i-1}{k-i}w^{k-i}+wf_{i+1}
\]
得到
\[f_i=(w+1)f_i+\dbinom{n-i-1}{k-i}w^{k-i}
\]
所以
\[ans=\sum\limits_{i=1}^{k}\dbinom{n}{i}i^k2^{n-i}f_i
\]
\(f_i\)可以\(O(k)\)递推了，\(i^k\)是积性函数可以线性筛
CF932E
原文：https://www.cnblogs.com/knife-rose/p/13055962.html
