CF932E Team Work

一、题目

点此看题

二、解法

水题，乱推，第二类斯特林数展开次方式： $$\sum _{i=1}^{n}C(n,i)\sum _{j=0}^{m}C(i,j)\times j!\times S(m,j)$$$$\sum _{i=1}^n\sum _{j=0}^{m}C(n,j)\times C(n-j,i-j)\times j!\times S(m,j)$$$$\sum _{j=0}^{m}C(n,j)\times j!\times S(m,j)\sum _{i=j}^{n}C(n-j,i-j)$$仔细观察，最后面那一项实际上是对杨辉三角一整行的求和，所以： $$\sum _{j=0}^{m}C(n,j)\times j!\times S(m,j)\times 2^{n-j}$$然后有手就行，组合数第二维不大直接算（但是我第一回斯特林数写错了嘤嘤嘤）。

#include <cstdio> #include <algorithm> using namespace std; const int M = 5005; const int MOD = 1e9+7; #define int long long int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,m,ans,A=1,S[M][M]; void init() { S[0][0]=1; for(int i=1;i<=m;i++) for(int j=1;j<=i;j++) S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%MOD; } int qkpow(int a,int b) { int r=1; while(b>0) { if(b&1) r=r*a%MOD; a=a*a%MOD; b>>=1; } return r; } signed main() { n=read();m=read(); init(); for(int j=0;j<=m;j++) { ans=(ans+A*S[m][j]%MOD*qkpow(2,n-j)%MOD)%MOD; A=A*(n-j)%MOD; } printf("%lld\n",ans); }