Codeforces 932E:第二类斯特林数

题意：n、k为常数，模为1e9+7，求：

∑i=1N(ni)∗ik

题解：将i^k用斯特林数展开并化简之。

nk=∑i=1kS2(k,i)∗ni− 该公式的组合意义是：用n种颜色给k个不同的球染色，方案总数为n^k，算两次：先将球划分到不同集合中，然后给每个集合赋颜色。注意这个公式是ok的，因为n的i次下降幂，如果i>n则乘数有0，则值为0。

于是：

∑i=1n(ni)∗ik =∑i=1n(ni)∗∑j=1kS2(k,j)∗ij− =∑i=1n∑j=1kCin∗Aji∗S2(k,j) =∑j=1kS2(k,j)∗∑i=1nCin∗Aji 一般的套路就是把组合数部分放到一起去，根据组合数的公式或者组合意义来化简掉组合数部分。

本题考虑组合意义：C(n,i)为从n个球选出i个，A(i,j)可以理解为从刚刚选出的i个中选出j个做排列。考虑到后边这个求和式中j为常量，则等价于从n个球中选出j个做排列，其余的数字选或不选均可。于是

∑i=1nCin∗Aji=Ajn∗2n−j 进而 ∑j=1kS2(k,j)∗∑i=1nCin∗Aji=∑j=1kS2(k,j)∗Ajn∗2n−j 现在已经可以O(k^2)地求值了。注意那个A(n,j)是下降幂，这里为了方便理解才这么写的，当j>n的部分可以不计算，因为下降幂=0.如果不加这个break条件的话。。。需要注意快速幂指数为负会死循环。。。。

Code:

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int MOD = 1e9+7; const int maxk = 5005; int n,k; LL s[maxk][maxk]; LL power(LL x,LL y){ LL ans =1; while (y){ if (y&1){ ans = ans*x%MOD; } x = x * x % MOD; y>>=1; } return ans; } int A(int x,int y){ LL ans =1; for (int i=x-y+1;i<=x;i++){ ans = ans*i%MOD; } return ans; } void init(){ s[1][1]=1; for (int i=2;i<maxk;i++){ for (int j=1;j<=i;j++){ s[i][j] = s[i-1][j-1]+j*s[i-1][j]%MOD; s[i][j]%=MOD; } } } int main(){ cin>>n>>k; init(); LL ans =0; for (int j=1;j<=k;j++){ if (j>n)break; ans = (ans+s[k][j]*A(n,j)%MOD*power(2,n-j)%MOD+MOD)%MOD; } cout<<ans<<endl; return 0; }