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

· · 题解

思路

看到括号不难想到卡特兰数，再看样例可以发现卡特兰数是对的。

所以不难发现 n 个好对的数量是对应卡特兰数的第 n 项。

接下来，每次确定好对位置，因为是操作二形成的，所以可以看成是剥离出来的一个子问题。

每次再把每个子问题的答案相乘即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
    int res = 0,f = 1;
    char ch = getchar();
    while (ch<'0'||ch>'9') f = (ch=='-'?-1:1),ch = getchar();
    while (ch>='0'&&ch<='9') res = (res<<3)+(res<<1)+(ch^48),ch = getchar();
    return res*f;
}
void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    if (x>9) write(x/10);
    putchar(x%10+'0');
}
void writech(int x,char ch){write(x),putchar(ch);}
const int N = 1e4+5,MOD = 998244353;
int n;
int t[N],cnt[N];
int fac[N],c[N];
int qpow(int a,int b)
{
    int res = 1;
    while (b)
    {
        if (b&1) res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
int inv(int a,int m)
{
    return qpow(a,m-2);
}
int C(int n)
{
    return fac[2*n]*inv(fac[n],MOD)%MOD*inv(fac[n+1],MOD)%MOD;
}
signed main()
{
    fac[0]=1;
    for (int i = 1; i < N; i++) fac[i]=fac[i-1]*i%MOD;
    for (int i = 0; i < N; i++) c[i]=C(i);
    int T=read();
    while (T--)
    {
        n=read();
        for (int i = 1; i <= 2*n; i++) t[i]=0;
        writech(c[n],' ');
        for (int i = 1; i <= n; i++)
        {
            int l=read(),r=read();
            for (int j = 0; j <= n; j++) cnt[j]=0;
            t[l]=i,t[r]=-i;
            stack<int> s;
            s.push(0);
            for (int j = 1; j <= 2*n; j++)
            {
                if (t[j]==0) ++cnt[s.top()];
                else if (t[j]<0) s.pop();
                else s.push(t[j]);
            }
            int ans = 1;
            for (int j = 0; j <= n; j++) ans=ans*c[cnt[j]/2]%MOD;
            writech(ans,' ');
        }
        puts("");
    }
    return 0;
}