luogu的Romtejudge挂了我就当我过了吧
求
\[\sum_{i=1}^n\binom{n}{i}i^k
\]
\]
其实是个思博套路题，但是我现在这个水平还是刷刷板子吧
处理\(x^k\)是一个套路了
\[x^k=\sum_{i=1}^k\begin{Bmatrix} k \\i \end{Bmatrix}\binom{x}{i}i!
\]
\]
于是
\[\sum_{i=1}^n\binom{n}{i}i^k=\sum_{i=1}^n\binom{n}{i}\sum_{j=1}^k\begin{Bmatrix} k \\j \end{Bmatrix}\binom{i}{j}j!
\]
\]
交换一下求和符号
\[\sum_{j=1}^n\begin{Bmatrix} k \\j \end{Bmatrix}j!\sum_{i=1}^n\binom{n}{i}\binom{i}{j}
\]
\]
后面这个\(\sum_{i=1}^n\binom{n}{i}\binom{i}{j}\)也是套路了，我们考虑一下组合意义，发现这个东西就是\(2^{n-j}\binom{n}{j}\)
我们再拆一下组合数，就得到了
\[\sum_{j=1}^k\begin{Bmatrix} k \\j \end{Bmatrix}2^{n-j}n^{\underline j}
\]
\]
这个题的\(k\leq5000\)，而且模数还不是ntt模数，于是直接递推就好了
递推的边界条件是\(\begin{Bmatrix} 0 \\0\end{Bmatrix}=1\)
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int n,k;
const int mod=1e9+7;
const int inv=500000004;
inline int ksm(int a,int b) {
int S=1;
while(b) {if(b&1) S=1ll*S*a%mod;b>>=1;a=1ll*a*a%mod;}
return S;
}
int S[2][5005];
int main() {
scanf("%d%d",&n,&k);
S[0][1]=1;int o=0;
for(re int i=2;i<=k;i++,o^=1)
for(re int j=1;j<=i;j++)
S[o^1][j]=(S[o][j-1]+1ll*S[o][j]*j%mod)%mod;
int ans=0,now=ksm(2,n-1),t=n,tot=n-1;
for(re int i=1;i<=min(n,k);i++,--tot) {
ans=(ans+1ll*S[o][i]*t%mod*now%mod)%mod;
t=1ll*t*tot%mod;now=1ll*now*inv%mod;
}
printf("%d\n",ans);
return 0;
}