@ysner
2018-09-19T11:48:51.000000Z
字数 1182
阅读 2009
数论
求
很显然能看出式子的现实意义:从个箱子中选出个,然后再在这个箱子中任意放入个球。
这样箱子有区别,球也有区别。
注意到比小了一个级别。考虑从球的角度下手。
个球最多只能放入个箱子,除此以外就是很多空箱。
因此,我们可以枚举球总共放入多少个箱子(不允许空箱),然后其它箱子是选与不选皆可。
设当前放入个箱子,则方案数为(表示排列数)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define db double
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=5005;
int n,k,S[5005][5005];
ll ans;
il int gi()
{
re int x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void Pre()
{
S[0][0]=1;
fp(i,1,k)
fp(j,1,i) S[i][j]=(S[i-1][j-1]+1ll*j*S[i-1][j]%mod)%mod;
}
il ll ksm(re ll S,re ll n)
{
re ll T=S;S=1;
while(n)
{
if(n&1) S=S*T%mod;
T=T*T%mod;
n>>=1;
}
return S;
}
il ll jc(re int l,re int r)
{
re ll res=1;
fp(i,l,r) (res*=i)%=mod;
return res;
}
int main()
{
n=gi();k=gi();
Pre();
fp(i,1,min(k,n))
(ans+=1ll*S[k][i]*jc(n-i+1,n)%mod*ksm(2,n-i)%mod)%=mod;
printf("%lld\n",ans);
return 0;
}