题解：AT_mujin_pc_2018_f チーム分け

LastKismet · 2025-08-22 13:07:19 · 题解

Sol

首先是 O(n^3) 做法，考虑简化一个组内 a 的限制，先按 a 从大到小排序，那么就只用考虑最后一个人即可，f_{i,j} 表示前 i 人中有 j 个人已经被分组的答案，转移枚举最后一组人数然后组合计数一下即可，最后答案即为 f_{n,n}。

然后不难发现 O(n^3) 直接就冲过去了。我后面的代码也是 n^3 的。

但还是简单讲一下 O(n^2\log n) 做法，f_{i,j} 表示分完大小 \ge i 的组之后有 j 个人已经被分组的方案，这么设计可以简单优化做到 O(n^2\log n)。

Code

const int N=1005;

int n;
int a[N];
mint f[N][N],fc[N],iv[N];
#define C(n,m) (fc[n]*iv[m]*iv[(n)-(m)])

inline void Main(){
    cin>>n;
    fc[0]=1;rep(i,1,n)fc[i]=fc[i-1]*i;
    iv[n]=1/fc[n];per(i,n,1)iv[i-1]=iv[i]*i;
    rep(i,1,n)cin>>a[i];
    sort(a+1,a+1+n,[](int a,int b){return a>b;});
    f[0][0]=1;
    rep(i,1,n)rep(j,0,i){
        f[i][j]=f[i-1][j];
        rep(k,1,min(a[i],j))f[i][j]+=f[i-1][j-k]*C(i-1-(j-k),k-1);
    }
    put(f[n][n]);
}