题解：CF2063F1 Counting Is Not Fun (Easy Version)

· · 题解

题目传送门

题目大意

有一个长度为 2n 的括号序列，每个位置一开始都不知道，给出 n 对匹配的括号，要求一开始和每轮线索后符合条件的括号序列数。

题目分析

注意到，答案跟卡特兰数有关，设 C(x) 来表示卡特兰数。

在没有线索时，答案就是 C(n)。当得到新的线索时，答案就会变成每段空位的卡特兰数相乘。例如：原本的括号序列 ???????? 变成 ??(??)??，答案就会从 C(4) 变成 C(2) \times C(1)，可以理解成每一层的空位拼起来，然后将每一层的卡特兰数相乘。

于是，我们可以括号序列常用的处理方法——栈，统计每一对括号里面的空位，最后乘起来即可。时间复杂度 \mathcal{O}(n ^ 2)。

注意：计算的时候，应该是 cnt[i] / 2 而不是 cnt[i]，因为卡特兰数 C(n) 是由 n 对括号构成的合法括号序列数。

code

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
    ll res = 0, f = 1; char ch = gc();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
    while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
    return res * f;
}
inline void write(ll x)
{
    if (x < 0) x = -x, pc('-');
    if (x > 9) write(x / 10);
    pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const ll mod = 998244353;
const int N = 5e3 + 5;
ll qpow(ll a, ll b = mod - 2)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll fac[N << 1], invf[N << 1], invi[N << 1];
ll Catalan(int x) { return fac[2 * x] * invf[x] % mod * invf[x] % mod * invi[x + 1] % mod; }
stack<int> stk;
void init()
{
    fac[0] = invf[0] = 1;
    for (int i = 1; i <= 10000; i++) fac[i] = fac[i - 1] * i % mod, invi[i] = qpow(i, mod - 2);
    invf[10000] = qpow(fac[10000]);
    for (int i = 9999; i >= 1; i--) invf[i] = invf[i + 1] * (i + 1) % mod;
    stk.push(0); // 最外层 
}
int l[N], r[N], p[N << 1], cnt[N];
// p 用来标记当前位置，0 为没固定，> 0 表示这是第几次加进来的 
// cnt 为第 i 对括号里面有多少个空位，那么这对括号的贡献为 Catalan(cnt_i / 2) 
// cnt_0 代表最外面有多少空位 
void solve()
{
    int n = read();
    for (int i = 1; i <= n; i++) l[i] = read(), r[i] = read();
    for (int i = 1; i <= 2 * n; i++) p[i] = 0;
    for (int j = 0; j <= n; j++)
    {
        for (int i = 0; i <= n; i++) cnt[i] = 0;
        p[l[j]] = j, p[r[j]] = -j; // 表示第 j 对括号 
        for (int i = 1; i <= 2 * n; i++)
        {
            if (p[i] == 0) cnt[stk.top()]++; 
            else if (p[i] > 0) stk.push(p[i]);
            else stk.pop();
        }
//      for (int i = 0; i <= n; i++) cout << cnt[i] << " ";
//      cout << endl;
        ll ans = 1;
        for (int i = 0; i <= n; i++) ans = ans * Catalan(cnt[i] / 2) % mod;
        writech(ans, ' '); 
    }
    pc('\n');
}
int main()
{
    init();
    int T = read();
    while (T--) solve();
    return 0;
}