CF2063F2 题解

Register_int · 2025-01-22 22:32:30 · 题解

没钦定的情况就是普通的括号序列计数，套卡特兰即可。事实上，强行先塞一对括号 [0,2n+1]，将每对括号 [l_i,r_i] 视为树上的一个节点 i，将每个对括号向被被他包含的下一层括号连边，就能得到一棵树。设 len_i=r_i-l_i+1，则一个点 u 内能自由放置的括号数量就是 val_u=len_u-2-\sum_{v\in\text{son}(u)} len_v。那么方案数为 \prod_i cat_{val_i}。

发现询问相当于在树上加点，这是困难的。不妨倒着做，转化为删一个点 u 并将其所有儿子连到他的父亲 fa_u 上。可以发现一次修改只会影响 u 和 fa_u 的 val，所以只要快速维护一个点的父亲是谁即可。可以使用并查集，删去 u 就将 u 与 fa_u 合并成一个点，时间复杂度 O(n\alpha(n))。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 6e5 + 10;
const int mod = 998244353;

int fac[MAXN], inv[MAXN], ifac[MAXN];

inline 
void init(int n) {
    inv[1] = 1;
    for (int i = 2; i <= n; i++) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
    *fac = *ifac = 1;
    for (int i = 1; i <= n; i++) fac[i] = (ll)fac[i - 1] * i % mod;
    for (int i = 1; i <= n; i++) ifac[i] = (ll)ifac[i - 1] * inv[i] % mod;
}

inline 
int c(int n, int m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return (ll)fac[n] * ifac[m] % mod * ifac[n - m] % mod; 
}

inline int f(int n) { return (ll)fac[n] * ifac[n / 2] % mod * ifac[n / 2] % mod * inv[n / 2 + 1] % mod; }
inline int invf(int n) { return (ll)ifac[n] * fac[n / 2] % mod * fac[n / 2] % mod * (n / 2 + 1) % mod; }

int T, n, a[MAXN], t[MAXN], tp;

int fa[MAXN], val[MAXN], p[MAXN], ans[MAXN], res;

int find(int u) { return u == p[u] ? u : p[u] = find(p[u]); }

int main() {
    for (scanf("%d", &T), init(6e5); T--; ) {
        scanf("%d", &n), *val = 0, res = 1;
        for (int i = 1; i <= n * 2; i++) a[i] = 0;
        for (int i = 1, l, r; i <= n; i++) scanf("%d%d", &l, &r), a[l] = a[r] = i;
        for (int i = 1; i <= n; i++) p[i] = i;
        for (int i = 1; i <= n * 2; i++) {
            if (!a[i]) { val[t[tp]]++; continue; }
            if (t[tp] != a[i]) t[++tp] = a[i], val[a[i]] = 0;
            else fa[a[i]] = t[--tp];
        }
        for (int i = 0; i <= n; i++) res = (ll)res * f(val[i]) % mod;
        ans[n + 1] = res;
        for (int i = n; i; i--) {
            int u = find(fa[i]); p[i] = u;
            res = (ll)res * invf(val[i]) % mod * invf(val[u]) % mod;
            ans[i] = res = (ll)res * f(val[u] += val[i] + 2) % mod;
        }
        for (int i = 1; i <= n + 1; i++) printf("%d ", ans[i]); puts("");
    }
}