又是数数的一天

lizihan250 · 2025-11-27 20:23:37 · 题解

题目大意：给定一个可重集合 a，将其划分为若干可重集合，从每个集合中选出一个众数组成可重集合 s。问有多少个合法的 s。

考虑怎样的 s 是合法的。

对于每个数 x，记它在 a 中的出现次数为 t_x。

显然的，对于任意的在 s 中出现的 x，只要不出现超过 t_x，它总是合法的。原因是可以先构造 t_x - 1 个集合，每个集合里放一个 x，然后最后一个集合放剩下的 x。

那么没有在 s 中出现的 x 呢？它们出现的次数上限等于每个集合中有效元素之和（不然 x 就成其中一个集合的唯一众数了），也就是说，t_x \le \sum \limits_{y \in S} t_y，这里同一个 y 求和时只算一次。

于是我们考虑 a 中出现次数最多的元素。如果它被选上，则其它元素任选多少个，或是不选，都是可行的，直接计算答案数即可。如果它没被选上，则要求剩下选出的数在 a 中的出现次数之和不小于它。这一部分可以使用背包进行计数，时间复杂度 O(n^2)。两部分答案相加即可得到最终答案。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=5000,mod=998244353;
int T,n,cnt[Maxn+10];
long long ans;
long long f[Maxn+10];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cnt[i]=0;
        int mx=0,p;
        for(int i=1,x;i<=n;i++)
        {
            cin>>x;
            cnt[x]++;
        }
        for(int i=1;i<=n;i++)
            if(cnt[i]>mx) mx=cnt[i],p=i;
        ans=mx;
        for(int i=1;i<=n;i++)
            if(i!=p) ans=(ans*(cnt[i]+1))%mod;
        for(int i=1;i<=n;i++)
            f[i]=0;
        f[0]=1;
        for(int i=1;i<=n;i++)
        {
            if(i==p) continue;
            for(int j=n-mx;j>=0;j--)
                f[j+cnt[i]]=(f[j+cnt[i]]+f[j]*cnt[i]%mod)%mod;
        }
        for(int i=mx;i<=n-mx;i++)
            ans=(ans+f[i])%mod;
        cout<<ans<<"\n";
    }
    return 0;
}