CF932E Team Work 题解

提供一片不需要推式子的题解。

前置知识，第二类斯特林数，$S(n,m)$表示 把 $n$ 个不同的小球放在 $m$ 个相同的盒子里方案数。

嗯， 我们给问题加上情景，看不懂英文，不保证和题目的情景一样。

有 $n$ 个箱子 $k$ 个球，每次选出 $i$ 个箱子，将 $k$ 个球随机放入 $i$ 个箱子，可以发现这玩意就是$ \sum_{i=1}^n\binom n i \times i^k $

首先要明确的是，一种放求的方式不一定只提供一种答案，例如当 $n=3,k=2$ 时:

• $i=2$ 选择 1、2 号箱子，每个箱子放一个球。
• $i=3$ 选择 1、2、3 号箱子，选 1、2 号箱子放一个球。

这两种情况球都在 1、2 号箱子中，但由于 $i$ 不同，所以属于不同的情况。

发现 $k$ 很小，枚举一共多少个箱子放了球。

设当前 $x$ 个箱子被放了球，

• 首先要在 $n$ 个箱子中选出 $x$ 个，方案数 $C_n^x$。
• 在这 $x$ 个箱子中，要放入 $k$ 个球，但与第二类斯特林数不同的是，箱子是不同的，所以要乘上箱子的全排列 $A_x^x$， 最终选择方案数 $S(k,x)\times A_x^x$
• 这 $x$ 个箱子放了球，但其他 $n-x$ 个箱子可能没选，也可能选了但没放，所以两种情况 $2^{n-x}$。

所以答案为： $$ \sum_{x=1}^kS(k,x)\times A_x^x \times C_n^x \times 2^{n-x} $$ 到这之后就可以直接算了，但也可以化简。

发现： $$ A_x^x\times C_n^x=x!\times \frac{n!}{x!(n-x)!}=\frac{n!}{(n-x)!} $$ 从 $n$ 向 $n-x+1$ 累成即可。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int p=1e9+7;
int n,k;
ll s[5010][5010],ans;
ll qpow(ll x,int y){
    ll ans=1;
    while(y){
        if(y&1) ans=ans*x%p;
        y>>=1,x=x*x%p;
    }
    return ans;
}
int main(){
    cin>>n>>k;
    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-1]+s[i-1][j]*j)%p;}
    for(int i=1;i<=k&&i<=n;i++){
        ll t=s[k][i]*qpow(2,n-i)%p;
        for(int j=n-i+1;j<=n;j++) t=t*j%p;
        ans=(ans+t)%p;
    }
    cout<<ans;
}