CF932E Team Work

luogu $\{\}$为第二类$string$数 $$\sum _{i=1}^{n}C(n,i)\ast i^k$$ $$\sum _{i=1}^{n}C(n,i)\sum _{j=0}^{k}j!\ast \{k,j\}\ast C(i,j)$$ $$\sum _{i=1}^n\sum _{j=0}^{k}C(n,i)\ast C(i,j)\ast j!\ast \{k,j\}$$ $$\sum _{j=0}^{k}j!\ast \{k,j\}\sum _{i=1}^{n}C(n,i)\ast C(i,j)$$ $$\sum _{j=0}^{k}j!\ast \{k,j\}\sum _{i=1}^{n}C(n,j)\ast C(n-j,i-j)$$ $$\sum _{j=0}^{k}j!\ast \{k,j\}\sum _{i=1}^{n}C(n,j)\ast C(n-j,i-j)$$ $$\sum _{j=0}^{k}j!\ast \{k,j\}\ast C(n,j)\sum _{i=1}^{n}C(n-j,i-j)$$ $$\sum _{j=0}^{k}j!\ast \{k,j\}\ast C(n,j)\ast 2^{n-j}$$

#include <bits/stdc++.h> using namespace std; const int mo = 1e9+7; typedef long long LL; #define int LL const int maxk = 5e3+5; int readint(){ int x=0,f=1;char s=getchar(); #define sc (s=getchar()) while(s<'0'||s>'9'){ if(s=='-') f=-1; sc; } while(s>='0'&&s<='9'){ x=(x<<3)+(x<<1)+(s^48); sc; } #undef sc return x*f; } int C[maxk]; int fac[maxk]; int s[maxk][maxk]; int qkpow(int a,int b){ int ans=1; while(b){ if(b&1) ans=ans*a%mo; b>>=1; a=a*a%mo; } return ans; } void init(int n,int k){ C[1]=n;C[0]=1; for(int i=2;i<=k;i++) C[i]=C[i-1]*(n-i+1)%mo*qkpow(i,mo-2)%mo; s[0][0]=1; for(int i=1;i<=k;i++){ for(int j=1;j<=i;j++){ s[i][j]=(s[i-1][j]*j%mo+s[i-1][j-1])%mo; } } fac[1]=1; for(int i=2;i<=k;i++){ fac[i]=fac[i-1]*i%mo; } } signed main (){ int n=readint(),k=readint(); init(n,k); int pow_2=qkpow(2,n); int be=2; int ans=0; for(int j=1;j<=k;j++){ if(j>n) break; ans=(ans+fac[j]*s[k][j]%mo*C[j]%mo*pow_2%mo*qkpow(be,mo-2))%mo; be=be*2%mo; } cout<<ans<<endl; return 0; }