题意：给定 $n,k$，求 $sumlimits^n_{i=1}dbinom{n}{i}i^kmod(10^9+7)$。
$1le nle 10^9,1le kle 5000$。
很水的一道题。
根据第二类斯特林数的性质：
$$n^k=sum^k_{i=1}egin{Bmatrix}k\iend{Bmatrix}i!dbinom{n}{i}$$
那么直接套进去：
$$sumlimits^n_{i=1}dbinom{n}{i}sum^k_{j=1}egin{Bmatrix}k\jend{Bmatrix}j!dbinom{i}{j}$$
$$sum^k_{j=1}egin{Bmatrix}k\jend{Bmatrix}j!sumlimits^n_{i=j}dbinom{n}{i}dbinom{i}{j}$$
$$sum^k_{j=1}egin{Bmatrix}k\jend{Bmatrix}j!sumlimits^n_{i=j}dfrac{n!}{i!(n-i)!}dfrac{i!}{j!(i-j)!}$$
$$sum^k_{j=1}egin{Bmatrix}k\jend{Bmatrix}j!sumlimits^n_{i=j}dfrac{n!}{(n-i)!}dfrac{1}{j!(i-j)!}$$
$$sum^k_{j=1}egin{Bmatrix}k\jend{Bmatrix}j!sumlimits^n_{i=j}dfrac{n!}{j!(n-j)!}dfrac{(n-j)!}{(n-i)!(i-j)!}$$
$$sum^k_{j=1}egin{Bmatrix}k\jend{Bmatrix}j!sumlimits^n_{i=j}dbinom{n}{j}dbinom{n-j}{i-j}$$
$$sum^k_{j=1}egin{Bmatrix}k\jend{Bmatrix}j!dbinom{n}{j}sumlimits^n_{i=j}dbinom{n-j}{i-j}$$
$$sum^k_{j=1}egin{Bmatrix}k\jend{Bmatrix}j!dbinom{n}{j}sumlimits^{n-j}_{i=0}dbinom{n-j}{i}$$
$$sum^k_{j=1}egin{Bmatrix}k\jend{Bmatrix}j!dbinom{n}{j}2^{n-j}$$
如果我们知道了所有的 $egin{Bmatrix}k\jend{Bmatrix}$ 那么这个式子可以做到 $O(klog n)$。
而预处理这些斯特林数可以用 $k^2$ 递推，当然也可以用卷积做到 $klog k$。
由于本题 $k^2$ 已经足够，而且模数不友好，直接递推就好了。
时间复杂度 $O(k^2+klog n)$。
#include<bits/stdc++.h> using namespace std; const int mod=1000000007; #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define ROF(i,a,b) for(int i=(a);i>=(b);i--) #define MEM(x,v) memset(x,v,sizeof(x)) inline int read(){ int x=0,f=0;char ch=getchar(); while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return f?-x:x; } int n,k,S[5050][5050]; inline int qpow(int a,int b){ int ans=1; for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod; return ans; } int main(){ n=read();k=read(); S[0][0]=1; FOR(i,1,k) FOR(j,1,i) S[i][j]=(S[i-1][j-1]+1ll*S[i-1][j]*j)%mod; int c=1,f=1,ans=0; FOR(i,1,min(n,k)){ c=1ll*c*(n-i+1)%mod*qpow(i,mod-2)%mod; f=1ll*f*i%mod; ans=(ans+1ll*c*S[k][i]%mod*f%mod*qpow(2,n-i))%mod; } printf("%d ",ans); }