题解 CF932E 【Team Work】

· · 题解

将原题看作：有n个箱子，从中选出i个箱子，然后把k个不同的球装在这i个箱子中，求方案数。

发现k个球最多装在k个箱子里，会有很多空箱，所以设f(i,j)表示i个球装在j个箱子里，没有空箱的方案数，那么答案会变成：

\sum_{i=1}^k f(k,i)2^{n-i}

这样一个f(i,j)让我们想起第二类斯特林数。当然，选择哪j个箱子还有待确定，所以答案就是：

\sum_{i=1}^k S(k,i)\frac{n!}{(n-k)!} 2^{n-i} 
#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int mod=1000000007;
int n,K,ans;
int S[5005][5005];
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
void prework() {
    S[0][0]=1;
    for(RI i=1;i<=K;++i)
        for(RI j=1;j<=i;++j)
            S[i][j]=(S[i-1][j-1]+1LL*j*S[i-1][j]%mod)%mod;
}
int main()
{
    scanf("%d%d",&n,&K),prework();
    for(RI i=1;i<=n&&i<=K;++i) {
        int kl=1LL*S[K][i]*ksm(2,n-i)%mod;
        for(RI j=n-i+1;j<=n;++j) kl=1LL*kl*j%mod;
        ans=(ans+kl)%mod;
    }
    printf("%d\n",ans);
    return 0;
}