专栏文章

又是数数的一天

llizihan250
CF2165B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzdkj3
此快照首次捕获于
2025/12/01 18:02
3 个月前
此快照最后确认于
2025/12/01 18:02
3 个月前
查看原文
题目大意：给定一个可重集合 aa，将其划分为若干可重集合，从每个集合中选出一个众数组成可重集合 ss。问有多少个合法的 ss。
考虑怎样的 ss 是合法的。
对于每个数 xx，记它在 aa 中的出现次数为 txt_x。
显然的，对于任意的在 ss 中出现的 xx，只要不出现超过 txt_x，它总是合法的。原因是可以先构造 tx−1t_x - 1 个集合，每个集合里放一个 xx，然后最后一个集合放剩下的 xx。
那么没有在 ss 中出现的 xx 呢？它们出现的次数上限等于每个集合中有效元素之和（不然 xx 就成其中一个集合的唯一众数了），也就是说，tx≤∑y∈Styt_x \le \sum \limits_{y \in S} t_y，这里同一个 yy 求和时只算一次。
于是我们考虑 aa 中出现次数最多的元素。如果它被选上，则其它元素任选多少个，或是不选，都是可行的，直接计算答案数即可。如果它没被选上，则要求剩下选出的数在 aa 中的出现次数之和不小于它。这一部分可以使用背包进行计数，时间复杂度 O(n2)O(n^2)。两部分答案相加即可得到最终答案。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...