题解：CF2165B Marble Council

前言

Div.2 D 和 E 没做出来，掉了 27 分

严肃建议 swap Div.2 D，E

Solution

考虑判定一个多重集结果是否合法，发现如果一个数出现在了结果中，那它是不重要的，出现了几次无所谓，手玩一下发现是很容易构造的，出现 1 次就是全部挑出来分成一个子集，出现 2 次就是全部挑出来分成两个子集，等等。

但如果一个数未出现在结果中，那它显然有要求，即不能是任意一个子集中的唯一一个 mode（或者说众数）。

那怎样才能满足这一条件呢？形象化的理解，我们要把这个未出现的数塞进一些子集中，且每个子集塞的数量不能超过原来子集众数的出现次数，那最大的容量就是所有出现了的数的数量之和，这个容量显然不应小于未出现的数的数量。

形式化地：

记生成的新多重集为。
记未出现在中的数的数量之和为，出现在中的数的数量之和为。
记元素在原多重集中的个数为。

若：

对于，都有。

则是合法的。

简单转化可得：

记为，则有：

很好看的结论，对吧？但还看不出来有什么用，那接下来，我们来考虑在已经选定一个方案，确定哪些数出现，哪些数不出现的情况下有多少贡献。

这时注意开头的一句话：

如果一个数出现在了结果中，那它是不重要的，出现了几次无所谓

也就是说，对于，可以出现次，完全任意。

那方案贡献就呼之欲出了，就是出现在中的数的出现次数之积。

至此，我们已经想通了「如何判定一个方案是否可行」以及「一个方案的贡献是多少」，最后一步自然就是结合起来计算答案了。

发现判定条件中有一个令人烦躁的，最大值不好确定，那我们就想把它摁住，于是将数组去零并以升序排序（显然需要去零，根本不存在的数不应考虑）。

现在枚举，当前所枚举的这一位，我们将其钦定为，发现前面小于的可选，而后面的全不选，且前面所选元素之和小于等于。

于是发现这就是个01背包动态规划，状态定义是普通的，只提一下初始化和转移。

初始化，转移。

有点反直觉，但并不难理解，初状态就是所有数均出现，计数就是所有数的出现次数乘积，转移是让一个数不出现，因此贡献除以其出现次数。

最后统计答案（表示中非零元素的个数）：

注意事项：

记得滚动数组优化，因而要一边 DP 一边统计答案。
除法要用逆元实现。

时间复杂度分析

显然的。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const LL mod = 998244353;
LL n;
LL a[5005], cnt[5005];
LL f[5005];   // 滚动数组优化
LL inv[5005]; // 逆元
void init()
{
    inv[1] = 1;
    for (int i = 2; i <= 5000; i++)
        inv[i] = (mod - mod / i) * (inv[mod % i]) % mod;
}
void solve()
{
    for (int i = 1; i <= n; i++)
        cnt[i] = 0, f[i] = 0;

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
    }
    vector<int> v; // 去零并排序后的 cnt
    v.emplace_back(0);
    f[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (cnt[i])
        {
            v.emplace_back(cnt[i]);
            f[0] = f[0] * cnt[i] % mod; // 所有数均出现，贡献为 cnt 中所有非 0 元素之积
        }
    }
    sort(v.begin(), v.end());
    int m = v.size() - 1;
    LL ans = f[0];
    for (int i = 1; i <= m; i++)
    {
        if (v[i] * 2 > n)
            continue;
        for (int j = 0; j <= n - 2 * v[i]; j++)
        {
            ans += (f[j] * inv[v[i]]) % mod;
            ans %= mod;
        }
        for (int j = n; j >= v[i]; j--)
        {
            f[j] += (f[j - v[i]] * inv[v[i]] % mod);
            f[j] %= mod;
        }
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}