这题的 \(O(k^2)\) 很板啊，三四分钟就推完了。
\[\sum_{i=1}^{n}\begin{pmatrix}n\\i\end{pmatrix}i^k \]发现 \(k\) 可以接受 \(O(k^2)\)，那不得直接斯特林。
\[= \sum_{i=1}^{n}\begin{pmatrix}n\\i\end{pmatrix}\sum_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\begin{pmatrix}i\\j\end{pmatrix} \]\[= \sum_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=1}^{n}\begin{pmatrix}n\\i\end{pmatrix}\begin{pmatrix}i\\j\end{pmatrix} \]组合意义推导，得到：
\[\sum_{i=1}^{n}\begin{pmatrix}n\\i\end{pmatrix}\begin{pmatrix}i\\j\end{pmatrix} = 2^{n - j}\begin{pmatrix}n\\j\end{pmatrix} \]所以原式：
\[= \sum_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!2^{n - j}\begin{pmatrix}n\\j\end{pmatrix} \]\(O(k^2)\) 预处理斯特林数，\(O(k\log{n})\) 求解。
#include<bits/stdc++.h>
#define int long long
const int mod = 1e9 + 7;
using namespace std;
int s[5005][5005],fac[5005];
int dnpw[5005];
int fpow(int a,int b=mod-2)
{
int r=1;
while(b)
{
if(b&1)r=r*a%mod;
a=a*a%mod;
b>>=1;
}
return r;
}
int c(int n,int m)
{
return dnpw[m] % mod * fpow(fac[m]) % mod;
}
int n,k;
signed main()
{
cin >> n >> k;
s[0][0] = fac[0] = 1;
dnpw[0] = 1;
for(int i=1;i<=k;i++)
{
fac[i] = fac[i-1] * i % mod;
s[i][0] = 0;
dnpw[i] = dnpw[i-1] * (n - i + 1) % mod;
for(int j=1;j<=i;j++)
{
s[i][j] = (s[i-1][j-1] + s[i-1][j] * j % mod) % mod;
}
}
int ans = 0;
for(int j=0;j<=min(n,k);j++)
{
ans = (ans + s[k][j] * fac[j] % mod * fpow(2,n-j) % mod * c(n,j) % mod) % mod;
}
cout<<ans;
return 0;
}