CF1740F Conditional Mix 题解

· · 题解

首先若可重集内元素个数不满 n 个，可以通过补 0 补到 n 个。同时我们发现，对于可重集内两个集合 i,j，若集合大小分别为 M_i 和 M_j 且 M_i>M_j，则 i 中存在一个数可以取出放入 j 中。也就是说对于两个可重集 M,N，如果对于 \forall 1\le k\le n 都有 \sum_{i=1}^k M_i\ge\sum_{i=1}^k N_i，那么若 M 能被表示出来则 N 也可以被表示。

那么 \sum_{i=1}^k M_i 的上界是多少呢？对于出现次数小于 k 的数，肯定是可以都选的；对于出现次数大等于 k 的数，至多只能选 k 个。所以假设 cnt_i 表示 i 出现的次数，那么 \sum_{i=1}^k M_i\le\sum_{i=1}^n \min(k,cnt_i)，同时不难构造出一个可重集 M 使得等号都成立，因此问题转化为求满足该条件的集合有多少个。

从大到小选数。设 f_{i,j,k} 表示前 i 个，和为 j，已选的最小的数为 k，转移可以用前缀和优化至 O(1)。同时注意到第一维可以滚动掉，且 k\le\frac{n}{i}，那么总时间复杂度就是 O(n^2\ln n) 的，空间复杂度 O(n^2)。

Code

#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int n,i0=0,i1=1;
int a[2002],cnt[2002],sum[2002];
int f[2][2002][2002];
inline bool cmp(int x,int y)
{
    return x>y;
}
inline void upd(int &x,int y)
{
    if((x+=y)>=mod)x-=mod;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]),++cnt[a[i]];
    sort(cnt+1,cnt+n+1,cmp);
    for(int i=0;i<=n;++i)for(int j=f[0][0][i]=1;j<=n;++j)sum[i]+=min(i,cnt[j]);
    for(int i=1,u;i<=n;++i,i0^=1,i1^=1)
    {
        u=n/i;
        for(int j=0;j<=sum[i];++j)f[i1][j][u+1]=0;
        for(int k=u;~k;--k)for(int j=0;j<=sum[i];++j)upd(f[i1][j][k]=(j>=k? f[i0][j-k][k]:0),f[i1][j][k+1]);
    }
    return 0&printf("%d",f[i0][n][0]);
}