题目链接
题意
有(n)个箱子，从中选出(i)个箱子，然后把(k)个不同的球装在这(i)个箱子中，求方案数。
实际上这题就是求:
[sum_{i=1}^nc_n^i*i^k
]
不知道为什么翻译直接把这个写出来了，莫名其妙。
直接求这个式子肯定不行，(n)很大会超时，所以我们应该化简式子
[sum_{i=1}^nc_n^i*i^k
]
[=sum_{i=0}^nc_n^i*i^k
]
根据第二类斯特林数的性质：
[n^k=sum_{i=0}^nS(k,i)*i!*C(n,i)
]
所以式子可以继续化简：
[=sum_{i=0}^nc_n^i*sum_{j=0}^kS(k,j)*j!*C(i,j)
]
[=sum_{i=0}^nc_n^i*sum_{j=0}^kS(k,j)*j!*frac{i!}{j!*(i-j)!}
]
[=sum_{i=0}^nc_n^i*sum_{j=0}^kS(k,j)*frac{i!}{(i-j)!}
]
[=sum_{i=0}^nfrac{n!}{i!(n-i)!}*sum_{j=0}^kS(k,j)*frac{i!}{(i-j)!}
]
[=sum_{i=0}^nsum_{j=0}^kS(k,j)*frac{i!}{(i-j)!}*frac{n!}{i!(n-i)!}
]
[=sum_{i=0}^nsum_{j=0}^kS(k,j)*frac{n!}{(i-j)!*(n-i)!}
]
[=sum_{j=0}^kS(k,j)sum_{i=0}^nfrac{(n-j)!}{(i-j)!*(n-i)!}*frac{n!}{(n-j)!}
]
[=sum_{j=0}^kS(k,j)sum_{i=0}^nC(n-j,n-i)*frac{n!}{(n-j)!}
]
[=sum_{j=0}^kS(k,j)*frac{n!}{(n-j)!}sum_{i=0}^nC(n-j,n-i)
]
[=sum_{j=0}^kS(k,j)*frac{n!}{(n-j)!}*2^{n-j}
]
所以这就可以直接做了
code
#include<cstdio>
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
typedef long long ll;
const int mod=1e9+7;
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return f*x;
}
ll s[5011][5011];
int n,k;
inline void init(){
s[0][0]=1;
for(rg int i=1;i<=k;i++)
for(rg int j=1;j<=i;j++)
s[i][j]=(s[i-1][j-1]+j*s[i-1][j])%mod;
}
inline ll ksm(int b){
ll ans=1,a=2;
while(b){
if(b&1)
ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans%mod;
}
main(){
n=read(),k=read();
init();
ll p=ksm(n),ans=0,js=1,inv=ksm(mod-2);
for(rg int i=0;i<=k;i++){
ans+=s[k][i]*p%mod*js,p*=inv,p%=mod;
ans%=mod;
js=js*(n-i)%mod;
}
printf("%lld",ans);
return 0;
}