CF1830C Hyperregular Bracket Strings

题意

给定 k 个区间，求有多少种长度为 n 的合法括号序列，满足每个区间也是合法括号序列。

题解

考虑两个相交的区间，可以分成三个区间，三个区间都满足是合法括号序列。

黑色是原本的，黄色是现在的。

考虑两个相包含的区间，被包含的区间是一部分，剩余部分是一部分。

红色部分要满足合法，黄色部分拼起来也要满足合法。

我们有一堆相交，相包含的区间交替出现，如果你要真的分割区间会是一个我不会的分讨。

我们考虑给每一个区间赋权值，相交部分的权值就异或起来。

在上面两种情况中权值异或后权值每一部分都不相同。

我们想要的是每一种区间的长度然后求卡特兰数，也就是每一种区间也就是每一个异或值对应的个数。

区间赋异或权值可以考虑差分序列，两端点赋了之后再前缀异或和得到原序列。

代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long  
using namespace std;
const int N = 3e5 + 10, mod = 998244353;
int T, n, k, l, r;
ull p[N], v;
ll pr[N], ip[N], ans = 1;
mt19937_64 myrand(20070924);
map<ull, int>t;
ll mpow(ll x, ll k){
    ll ans = 1;
    while(k){
        if(k & 1) ans = ans * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return ans;
}

void pre(int n){
    pr[0] = ip[0] = 1;
    for(int i = 1; i <= n; ++i) pr[i] = pr[i - 1] * i % mod;
    ip[n] = mpow(pr[n], mod - 2);
    for(int i = n - 1; i >= 1; --i) ip[i] = ip[i + 1] * (i + 1) % mod;
} 
ll C(int x, int y){ return pr[x] * ip[y] % mod * ip[x - y] % mod;}
ll Can(int n){
    if(n & 1) return 0;
    return (C(n, n / 2) - C(n, n / 2 - 1) + mod) % mod;
}
void input(){
    cin>> n >> k;
    for(int i = 1; i <= k; ++i){
        cin >> l >> r;
        v = myrand();
        p[l] ^= v, p[r + 1] ^= v;
    }
}
void op(){
    for(int i = 1; i <= n; ++i){
        p[i] ^= p[i - 1];
        ++t[p[i]];
    }
    for(auto it : t) ans = ans * Can(it.second) % mod;
}
void qk(){
    ans = 1;
    for(int i = 1; i <= n + 1; ++i) p[i] = 0;
    t.clear();
} 
int main(){
    pre(3e5);
    cin>>T;
    while(T--){
        input();
        op();       
        cout<<ans<<'\n';
        qk();
    }
}