1831-E 题目大意

给定一个整数\(n\)，和\(k\)个区间，区间端点范围在\([1,n]\)内。

如果有一个长为\(n\)合法的括号序列，且它的这\(k\)个区间\([l,r]\)中的子括号序列也是合法的，那么称这个括号序列是“好的”。

请你求出有多少个长度为\(n\)的“好的”括号序列，答案对\(998244353\)取模。

Solution

从简单的情况开始考虑：

\(1.k=0\)时：
容易知道一个长为\(2n\)的合法括号序列个数为卡特兰数\(\frac{1}{n+1}\binom{2n}{n}\)。

\(2.k=1时\)：
要求区间\([l,r]\)中是一个合法的括号序列，因为原括号序列也是合法的，那么我们将\([1,l]\)和\([r+1,n]\)两段拼起来也是一个合法的的括号序列，据乘法原理，把两个括号序列的卡特兰数乘起来就是总的方案数。

\(3.k=2时\)：
两个区间\([l_1,r_1],[l_2,r_2]\)其中\(l_1\le l_2\)，分三种情况：

• 两个区间相离\((r_1<l_2)\)：可以把整个括号序列分为三段，\([l_1,r_1],[l_2,r_2]\)以及除这两个区间之外的拼起来的一段，此时把三个括号序列的卡特兰数乘起来即为总方案数。
• 两个区间包含\((r_1>r_2)\)：可以把整个括号序列分为三段，\([l_2,r_2]\)一段，\([l_1,l_2-1]\)和\([r_2+1,r_1]\)拼起来的一段，\([1,l_1-1]\)和\([r_1+1,n]\)拼起来的一段，此时把三个括号序列的卡特兰数乘起来即为总方案数。
• 两个区间相交\((r_1\ge l_2 \;and\; r_1\le r_2)\)：这里序列\([l_2,r_1]\)被两个区间覆盖，那么要求这个序列也是一个合法的括号序列。此时可以把整个括号序列分为四段，\([l_1,l_2-1],[l_2,r_1],[r_1+1,r_2]\)以及\([1,l_1-1]\)和\([r_2+1,n]\)拼起来的一段，此时把四个括号序列的卡特兰数乘起来即为总方案数。

推广到一般，被相同的区间覆盖的点集应当被划分为一组，这些点对应的括弧拼起来是一个合法的括号序列，答案即把所有组的卡特兰数相乘。接下来要解决的是如何对各个点进行划分。

对于给定的一个区间\([l,r]\)，我们可以对这个区间打上标记，常用的做法是用差分数组，在数组的\(l\)位置打一个\(+1\)的标记，在\(r+1\)的位置打一个\(-1\)的标记。如果用加法的话，对于两个不相交的区间，其在差分数组中对应的区间标记都是\(+1\)，而实际上不能把这两个区间划分为同一组，这里的标记要用到一个\(trick\)——\(Xor\;Hashing\)。

对每个区间\([l,r]\)赋一个随机值\(x\)作为它的标记，然后在差分数组的\(l\)位置打一个\(\oplus x\)的标记，在\(r+1\)的位置也打一个\(\oplus x\)的标记($\oplus $是异或符号)。统一处理完所有区间后，对差分数组求前缀异或，即可得到每个点属于哪个分组，用哈希表统计每组中点的数量即可。最后把所有卡特兰数乘起来即可得到答案。

时间复杂度\(O(n+klogk·logmod)\)。这里用了\(map\)复杂度上多了个\(logk\)，\(logmod\)是求逆元的复杂度。

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

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod=998244353;

struct Comb{
    constexpr static int mod=998244353;
    vector<int> fac;
    int n;

    Comb(int _n):n(_n),fac(_n+1){
        get_fac();
    };

    ll pow(ll a,ll b){
        ll res=1;
        while(b){
            if(b&1) res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return res;
    }

    ll inv(ll x){
        return pow(x,mod-2);
    }

    void get_fac(){
        fac[0]=1;
        for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;
    }

    int comb(int n,int m){
        if(m>n) return 0;
        return 1LL*fac[n]*inv(1LL*fac[n-m]*fac[m]%mod)%mod;
    }
};

void solve(){
    int n,k;
    cin>>n>>k;
    vector<unsigned ll> d(n+1);
    for(int i=0;i<k;i++){
        int l,r;
        cin>>l>>r;
        l--;
        auto x=rng();
        d[l]^=x;
        d[r]^=x;
    }
    for(int i=1;i<=n;i++) d[i]^=d[i-1];
    map<unsigned ll,int> p;
    for(int i=0;i<n;i++) p[d[i]]++;
    ll ans=1;
    Comb C(n+1);
    for(auto [x,c]:p){
        if(c&1){
            ans=0;
        }else{
            ans=(ans*C.comb(c,c/2)%mod)*C.inv(c/2+1)%mod;
        }
    }
    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}