这道题需要用到一个组合数的公式:nk=∑i=0ns2{k,i}Anin^k=\sum_{i=0}^ns_2\{k,i\}A_n^ink=∑i=0ns2{ k,i}Ani
证明可以用组合意义:相当于是把k个不同的球放入k个不同的盒子里(每个盒子个数任意)的方案数等于先枚举使用盒子的个数i,然后把n个球分进i个盒子,然后给盒子编号。 所以原式=∑i=0nCni∗∑j=0ks2{k,j}Aij=\sum_{i=0}^nC_n^i*\sum_{j=0}^ks_2\{k,j\}A_i^j=∑i=0nCni∗∑j=0ks2{ k,j}Aij=∑i=0n∑j=0ks2{k,j}AijCni=\sum_{i=0}^n\sum_{j=0}^ks_2\{k,j\}A_i^jC_n^i=∑i=0n∑j=0ks2{ k,j}AijCni=∑j=0ks2{k,j}∑i=0kCniAij=\sum_{j=0}^ks_2\{k,j\}\sum_{i=0}^kC_n^iA_i^j=∑j=0ks2{ k,j}∑i=0kCniAij 然后又是套路,把后面一个求和公式用组合意义化简:∑i=0nCniAij\sum_{i=0}^nC_n^iA_i^j∑i=0nCniAij相当于先从n个数中选出来i个数来组合再从i个数中选出j个数来排列,注意这个地方j是定值。 那么从总体思考,相当于就是从n个数中选出了j个数来排列,剩下的n−jn-jn−j个数都可选可不选。 所以有:∑i=0nCniAij=Anj2n−j\sum_{i=0}^nC_n^iA_i^j=A_n^j2^{n-j}∑i=0nCniAij=Anj2n−j 所以推出原式=∑j=0ks2{k,j}Anj2n−j=\sum_{j=0}^ks_2\{k,j\}A_n^j2^{n-j}=∑j=0ks2{ k,j}Anj2n−j 至此,已经可以O(n2)O(n^2)O(n2)求出答案了。 代码:#include#define ri register intusing namespace std;const int mod=1e9+7,K=5e3+5;typedef long long ll;int ans=0,n,k,s2[K][K],up;inline void init(){ s2[1][1]=1,up=min(n,k); for(ri i=2;i<=k;++i)for(ri j=1;j<=i;++j)s2[i][j]=((ll)s2[i-1][j-1]+(ll)s2[i-1][j]*j%mod)%mod;}inline int ksm(int a,int p){ int ret=1;for(;p;p>>=1,a=(ll)a*a%mod)if(p&1)ret=(ll)ret*a%mod;return ret;}inline int A(int n,int m){ int ret=1;for(ri i=n-m+1;i<=n;++i)ret=(ll)ret*i%mod;return ret;}int main(){ scanf("%d%d",&n,&k),init(); for(ri i=1;i<=up;++i)(ans+=(ll)s2[k][i]*A(n,i)%mod*ksm(2,n-i)%mod)%=mod; cout<