题解 —— CF1666F Fancy Stack

· · 题解

前言：这破题我whk时放在脑子里想，但是又不是全神贯注的想，想的时候整个人也很不在状态，就这样想了三天想出来了。好像我很弱，一道蓝色的题想了三天，但是我觉得我很强，因为没人教我，我靠自己硬想完全没受到提示自学了计数dp。如果你去看 \rm Codeforces 官方题解你会觉得一帆风顺，但是实际上做题的时候还是会想到大量的错误路线。

我们设偶数块指一个编号为 i， 长为 b_i，其中 i 为偶数的块。奇数块同理。

我们首先观察一下本题有什么性质：奇数块小于相邻的两个偶数块，然而偶数块是严格上升的，所以只要保证每一个奇数块都小于上面的相邻的一个偶数块就行了。形式化的讲，对于 i 为奇数且 i \neq 1，只要保证 b_i < b_{i-1}，条件 1 就满足了。

我们接着想，除了最下面的偶数块和最上面的偶数块，每个偶数块都要找一个比他小的数和他配对。最下面的偶数块不用配对。最上面的偶数块要找两个数配对。比如题目中的例子，四个偶数块是 3、4、6、7，3 和 1、2 配对，4 和 1 配对，6 和 4 配对， 7 不用配对。很显然，b_n = \max\{a\}，所以最下面的偶数块就确定了。我们已经把原问题转化为了一个可以用计数dp解决的问题：从 n-1 个数中取出一个长为 \frac{1}{2}n-1 严格上升序列，再给序列中第一个数找出两个比它小的数配对，再给序列中剩余的数每个数找出一个比它小的数配对，问你有几种方案。

虽然可能讲的有点啰嗦，但目前的推导都是十分 \rm easy 的。

但凡你做过一两道 \rm OI 题，你都知道要把 a 排序，将元素的偏序关系转化为序列的前后关系。我们会发现 a 的元素是可以相等的，而作者我根本不知道怎么处理，所以作者认为应该去重，然后记录每个元素出现的次数。作者的代码中， m 就是去掉最下面的偶数块后，去重的元素个数。cnt[i] 就是 \rm rank 为 i 的数出现的次数（有点类似于离散化）。这个时候，读者应该是有点思路的。

设 f_{i, j} 是去掉 \max\{a\} 去重后（后面不提这个词，默认如此）前 j 大的数中，取 i 个做偶数块的合法方案数。合法的定义是，不会有奇数块没有比它大的数配对，但是可以有偶数块没用配对上。之所以这么设计dp状态，是因为不是前 j 大的数可以作为奇数块给前 j 大的偶数块配对。第 j 大的数可以有一个作为偶数块，也可以一个都不作为偶数块。前 j-1 大的偶数块部分已经配对好了，但是我们知道没配对好的数量：i-(pcnt_{j-1}-i)（pcnt_j 指前 j 大的数的 cnt 之和）。所以dp转移式就是：

f_{i, j} = {i-(pcnt_{j-1}-i) \choose cnt_j}f_{i, j-1} + {(i-1)-[pcnt_{j-1}-(i-1)] \choose cnt_j-1}f_{i-1, j-1}

我们已经快做完了。需要注意的是，最上面的偶数块要找俩奇数块配对。根据做题经验，我们可能是要更改dp状态和转移式。但这个问题要通过改状态转移式解决很烦，作者可能不够聪明，花了很多时间想怎样改状态设计。我们根本没必要这么麻烦，直接枚举最上面的偶数块的 \rm rank 就好了。确定最上面偶数块的 \rm rank 之后，就是个“几个不同颜色的球，每个有若干个，求有多少种排列”的问题。In case of you 实在没看懂，我给个最上面偶数块的 \rm rank = i 时的方案数（作者我代码用的是另一写法，殊途同归）：

\frac{(pcnt_{m}-pcnt_i)!}{\prod_{j=i+1}^{m}cnt_j!}{\frac{1}{2}n-2-[pcnt_{i-1}-(\frac{1}{2}n-2)] \choose cnt_i-1}f_{\frac{1}{2}n-2, i-1}

当然，我们每一步操作都要有紧密的逻辑性，如果你观察一下会发现我们删除 \max\{a\} 时没特判 \max\{a\} 不止一个（这样的话答案显然是 0），也没特判 n = 2 时我们上述的一切都不存在。还有你可以发现最后统计答案时可以 O(n)，但是作者我用了 O(n^2) 的写法，反正总时间复杂度 O(n^2)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef const int& cint;

const int N = 5000, MOD = 998244353;
int n, m;
int a[N+1], cnt[N+1], pcnt[N+1], f[N/2][N+1];
int fac[N+1], inv[N+1], invfac[N+1];

inline int add(cint a, cint b) {
    return (a+b)%MOD;
}
inline int mul(cint a, cint b) {
    return (ll)a*b%MOD;
}
void init() {
    fac[0] = 1;
    for(int i = 1; i <= N; ++i) fac[i] = mul(fac[i-1], i);
    inv[1] = 1;
    for(int i = 2; i <= N; ++i) {
        inv[i] = mul((MOD-MOD/i), inv[MOD%i]);
    }
    invfac[1] = 1;
    for(int i = 2; i <= N; ++i) {
        invfac[i] = mul(invfac[i-1], inv[i]);
    }
}
inline int C(cint n, cint m) {
    if(m < 0 || n < 0 || m > n) return 0;
    if(m == 0 || m == n) return 1;
    return mul(fac[n], mul(invfac[m], invfac[n-m]));
}

void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    sort(a+1, a+n+1, greater<int>());
    if(a[1] == a[2]) {
        printf("0\n"); return;
    }
    if(n == 2) {
        printf("1\n"); return;
    }
    m = 0; memset(cnt, 0, sizeof(cnt)); memset(f, 0, sizeof(f));
    for(int i = 2; i <= n; ++i) {
        if(a[i] != a[i-1]) ++m;
        ++cnt[m];
    }
    for(int i = 1; i <= m; ++i) {
        pcnt[i] = pcnt[i-1]+cnt[i];
    }
    f[0][0] = 1;
    for(int i = 1; i < n/2-1; ++i) {
        for(int j = i; j <= min(i*2, m-1); ++j) {
            f[i][j] = add(mul(C(i-(pcnt[j-1]-i), cnt[j]), f[i][j-1]), mul(C((i-1)-(pcnt[j-1]-(i-1)), cnt[j]-1), f[i-1][j-1]));
        }
    }
    int ans = 0;
    for(int i = n/2-1; pcnt[m]-pcnt[i] >= 2; ++i) {
        int tmp = 1;
        for(int j = i+1; j <= m; ++j) {
            tmp = mul(tmp, C(n/2-(pcnt[i]-(n/2-1))-(pcnt[j-1]-pcnt[i]), cnt[j]));
        }
        ans = add(ans, mul(mul(f[n/2-2][i-1], C(n/2-2-(pcnt[i-1]-(n/2-2)), cnt[i]-1)), tmp));
    }
    printf("%d\n", ans);
}

int main() {
    // freopen("in", "r", stdin);
    int t;
    scanf("%d", &t); init();
    while(t--) solve();
    return 0;
}