[数学] [dp优化] CF1740F Conditional Mix

· · 题解

首先，每次选择两个交集为空的集合合并，等价于最终将原集合恰好拆分为若干个集合，每个集合内部无重复元素。

不妨记这些集合为 A=\{M_1\dots M_n\}，假如不够就补 0 即可，令 |M_1|\ge |M_2|\dots \ge |M_n|。然后记 cnt_i 为原序列中元素 i 的出现次数。

考虑判定 A 是否合法，注意到非常重要的一点：假如存在 M_i>M_j，那么 M_i 中必然存在 M_j 中没有的元素，可以调整一元素，令 M_i-1 而 M_j+1。

于是不难想到，若有 S=\{N_1\dots N_n\}，且满足“字典序”（即从 i=1 开始比较集合大小）比 A 大，那么就能将 S 调整为 A，即 S 合法，A 一定合法。

于是考虑找到一个合法且“字典序”最大的集合 P，容易想到，贪心地从 i=1 开始尽量填满即可。

不过比较“字典序”还是太麻烦了，其实可以这样比较，假如 \forall i,\sum_{j=1}^i |N_j|\ge \sum_{j=1}^i |M_j|，那么就有 S>A。

对于刚刚构造的 P 集合，显然有 \sum_{j=1}^i |P_j|=\sum_{j=1}^n \min(i, cnt_j)。

我们记 P,A 前缀和分别为 Lim_i,pre_i，那么只要满足 \forall i,pre_i\le Lim_i 就有 A 合法。

于是就容易了，不妨设 f_{i,s,j} 为填了 A_1\dots A_i，且 pre_i=s,|A_i|=j 时，合法方案总数，转移考虑枚举 |A_{i-1}|=k\ge j 即可。

于是得到了 O(n^4) 暴力，可以前缀和优化至 O(n^3)，然后滚动数组滚掉第一维。由于 |A_i| 递减，所以有 j\le \frac Si，直接优化至 O(n^2\ln n) 级别。

代码

写的比较难看。

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

#define int long long
#define ADD(a, b) a = (a + b) % mod
const int N = 2e3 + 5, mod = 998244353;
int n, a[N], cnt[N], Lim[N], ans, f[2][N][N], g[N][N], s[N];

signed main(){
    cin >> n;
    for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]), ++cnt[a[i]];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            Lim[i] += min(i, cnt[j]);
    for(int S = 1; S <= Lim[1]; ++S) f[1][S][S] = 1;
    for(int i = 2; i <= n; ++i){
        int id = (i & 1), _id = (id ^ 1); 
        for(int S = 0; S <= Lim[i - 1]; ++S)
            for(int j = 0; j <= S / (i - 1); ++j)
                g[S][j] = (g[S][j - 1] + f[_id][S][j]) % mod, f[_id][S][j] = 0;
        for(int S = 0; S <= Lim[i]; ++S)
            for(int j = 0; j <= S / i; ++j)
                if(S - j <= Lim[i - 1] && j <= S - j)
                    f[id][S][j] = (g[S - j][min(S - j, (S - j) / (i - 1))] - g[S - j][min(j - 1, (S - j) / (i - 1))] + mod) % mod;
    }
    for(int i = 0; i <= n; ++i) ADD(ans, f[n & 1][n][i]);
    cout << ans;
    return 0;
}