题解：CF2165B Marble Council

· · 题解

设最终的多重集合为 S，题目即要求求不同的 S 的数量。

假设我们已经考虑了 i-1 个数，现在考虑到第 i 个数 x，我们有 2 种选择：

  1. 向 S 添加 x。
  2. 不向 S 中添加 x。

显然，第一种选择总是可行的，因为我们可以在拆分 a 时，将要添加的数拆分为一个单独的集合来确保它一定在 S 中。

考虑不加入某个 x。

设值为 x 的数总共有 cnt_x 个，那么，当要添加的 x 的数量为 1 到 cnt_x 时，总是通过拆分出若干个只含 x 的集合来达到目的。

因此，若已经向 S 中添加过 x，后面的 x 总是可以不被添加。

现在，考虑不加入所有的 x。

假设所有的 x 都未被加入，那么，所有的被划分的含 x 的集合中，x 都不是唯一众数，且需要其余的众数中有被选入最终集合 S 的。

考虑某个多重集合中被选入 S 的数在该集合的数为 c，那么该集合最多放 c 个为被选入 S 的数。

因此，对于某个被选入多重集合 S 的数 x，其最多为 cnt_x 个未被选入 S 的数提供存放的位置。

因此，对于一个 x \notin S，需要保证 cnt_x \le \sum_{y \in S} cnt_y

因此，一个最终集合 S 可以存在，需要：

\max_{x \notin S} cnt_x \le \sum_{y \in S} cnt_y

设 max\_cnt 为所有 cnt_x 中的最大值，则对于最终集合 S，满足 max\_cnt \le \sum_{y \in S} cnt_y 的 S 均可以达到。

因此，我们设 dp_i 为 \sum_{y \in S} cnt_y = i 的 S 的数量，则最终答案 res = \sum_{i=max\_cnt}^n dp_i。

考虑之前所有的 dp_i 都已经计算完成，现在要加入 cnt_x 个 x，则最终集合可以多出 1 到 cnt_x 个 x， 因此有 dp_i = cnt_x \cdot dp_{i-cnt_x}。

初始化 dp_0=1 后，依次加入 x 并统计答案即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

int const N = 5007;
int const P = 998244353;

int n;
int a[N],cnt[N];

LL dp[N];

void solve(){
    cin >> n;
    for(int i=1 ;i<=n ;i++)
        cin >> a[i];

    for(int i=1 ;i<=n ;i++) cnt[i]=0;
    for(int i=1 ;i<=n ;i++) cnt[a[i]]++;

    int max_cnt = 0;
    for(int i=1 ;i<=n ;i++)
        max_cnt = max(max_cnt ,cnt[i]);

    dp[0]=1;
    for(int i=1 ;i<=n ;i++) dp[i]=0;

    for(int i=1 ;i<=n ;i++) if(cnt[i]){
        for(int j=n ;j>=cnt[i] ;j--) {
            dp[j] = (dp[j] + 1LL*cnt[i]*dp[j-cnt[i]]%P )%P;
        }
    }

    LL res = 0;
    for(int i=max_cnt ;i<=n ;i++) 
        res = (res+dp[i])%P;

    cout << res << "\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while(T--) solve();
}