卡特兰数
一个长为 \(2n\) 的序列，填入括号，有多少种合法方案？
\(C_n=\sum_iC_iC_{n-i-1}\)，其中 \(C_0=C_1=1\)。
它的封闭形式是 \(C_n=\binom{2n}{n}-\binom{2n}{n-1}\)。
problem
给定一个长度 \(n\) 和 \(k\) 个子区间 \(\{[l1,r1],[l2,r2],…,[lk,rk]\}\)。
问有多少个长度为 \(n\) 的合法括号序列，使得每一个子区间也是合法的括号序列。
\(n,k\leq 2^{18}\)。
solution
考虑对于两个区间 \(A,B\)，记他们的交集为 \(C\)，则明显：\(C,A/C,B/C\) 都应该是合法括号序列。（分开讨论有交集和覆盖的情况）
如果两个位置覆盖的区间集合相同，说它们在同一个等价类里面。那么：在同一等价类的位置，连起来应该是合法括号序列。判断这个东西可以使用异或哈希，计算答案使用 Catalan 数。
code
点击查看代码
#include <random>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
const int P=998244353;
void red(LL&x){x%=P;}
LL mod(LL x){return (x%P+P)%P;}
LL qpow(LL a,LL b,int p=P){LL r=1;for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p; return r;}
template<int N,int P> struct C_prime{
LL fac[N+10],ifac[N+10];
C_prime(){
for(int i=fac[0]=ifac[0]=1;i<=N;i++) fac[i]=fac[i-1]*i%P;
ifac[N]=qpow(fac[N],P-2,P);
for(int i=N-1;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%P;
}
LL operator()(int n,int m){return fac[n]*ifac[m]%P*ifac[n-m]%P;}
};
C_prime<1<<20,P> binom;
unsigned long long C[1<<20],sum[1<<20];
mt19937_64 rng(0x0b2d4a2f);
int n,m;
int mian(){
for(int i=1,l,r;i<=m;i++){
scanf("%d%d",&l,&r);
unsigned long long w=rng();
sum[l]^=w,sum[r+1]^=w;
}
map<LL,int> s;
for(int i=1;i<=n;i++) s[sum[i]^=sum[i-1]]++;
LL ans=1;
for(auto p:s) red(ans*=C[p.second]);
printf("%lld\n",mod(ans));
return 0;
}
void reset(){
memset(sum,0,sizeof(LL)*(n+10));
}
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
for(int i=1;i<=1<<19;i++) C[i<<1]=binom(i<<1,i)-binom(i<<1,i-1);
for(scanf("%*d");~scanf("%d%d",&n,&m);reset(),mian());
return 0;
}