题解：AT_mujin_pc_2018_f チーム分け

· · 题解

神秘题目被神秘搬题人搬到 NOIP 模拟赛 T1。（所以模拟赛成了全原题模拟赛，难度：紫紫紫紫）

以为是签到题，做了 1h 30min 还是只会枚举。

可以考虑设计状态 f(i, j) 表示当前考虑了所有 a_k \ge i 的人，其中 j 人还未被匹配的方案数。

令 c(i) 为所有 a_k \ge i 的人的数量。

转移：考虑枚举 k（当前新组成多少个人数为 i 的组），然后考虑转移的系数，很显然要首先从 j + c(i) 中选出 ki 个人，然后排列这 ki 个人成 k 组，但是会算重组内的排列和组间的排列方案数也就是 (i!)^k k!。

f(i, j + c(i) - ki) \longleftarrow f(i + 1, j) \times \displaystyle\binom{j + c(i)}{ki} \frac{(ki)!}{(i!)^k k!}

注：转移可以化简为

f(i, j + c(i) - ki) \longleftarrow f(i + 1, j) \times \displaystyle \frac{j + c(i)}{(j + c(i) - ki)!(i!)^k k!}

:::info[\large{\mathbf{Code}}]{open}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e3 + 10, mod = 998244353;
int n, x, cnt[N], f[N][N], fact[N], infact[N];
int qmi(int a, int k) {
    int res = 1;
    while(k) {
        if(k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}
int main()
{
    scanf("%d", &n);
    fact[0] = infact[0] = 1;
    for(int i = 1; i <= n; i ++) {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = qmi(fact[i], mod - 2);
    }
    for(int i = 0; i < n; i ++) {
        scanf("%d", &x);
        cnt[x] ++;
    }
    f[n][0] = 1;
    for(int i = n; i; i --)
        for(int j = 0; j <= n; j ++)
            if(f[i][j]) {
                int v = j + cnt[i];
                int inv = (LL)f[i][j] * fact[v] % mod;
                for(int k = 0, t = 0; t <= v; k ++, t += i) {
                    f[i - 1][v - t] = (f[i - 1][v - t] + (LL)inv * infact[k] % mod * infact[v - t] % mod) % mod;
                    inv = (LL)inv * infact[i] % mod;
                }
            }
    printf("%d\n", f[0][0]);
    return 0;
}