CF1830C Hyperregular Bracket Strings

CF1830C Hyperregular Bracket Strings

对于括号序列 \(s\)，我们通常使用折线图来描述。

我们设 \(n+1\) 个点，第 \(i-1\) 个点到第 \(i\) 个点会经过 \(s_i\)。

考虑对于限制 \([l_i,r_i]\)，\([l_j,r_j]\)，倘若两者有交，我们可以寻找更多性质。

我们先假定 \(l_i \leq l_j \leq r_i \leq r_j\)，容易发现如下性质：

注意到 \(l_i - 1\) 和 \(r_i\) 高度相同，\(l_j - 1\) 和 \(r_j\) 高度相同。

同时 \(l_j - 1\) 的高度一定不小于 \(l_i - 1\) 和 \(r_i\) 的。

同理 \(r_j\) 的高度一定不小于 \(l_j - 1\) 和 \(r_i\) 的，所以两者高度相等。

根据上述内容，我们将区间拆分成了三段合法括号序列。

接下来考虑两个区间包含，容易发现此时去掉中间的部分两边拼起来可以形成括号序列。

考虑使用异或哈希，每次给 \([l_i,r_i]\) 整体异或一个随机数，我们声称：

• 值相同的所有位置构成合法括号序列

这是有道理的，复杂度 \(O(n \log n)\)。

//Ad astra per aspera
#include<iostream>
#include<cstdio>
#include<ctime>
#include<map>
#include<random>
using namespace std;
const long long mod=998244353;
mt19937_64 rnd(time(0));
unsigned long long sum[300010];
long long inv(long long num){
	long long pre=mod-2,ans=1;
	while(pre){
		if(pre&1){
			ans=ans*num%mod;
		}
		num=num*num%mod;
		pre>>=1;
	}
	return ans;
}
long long fact[300010],invfact[300010];
void init(int n){
	fact[0]=invfact[0]=1;
	for(int i=1;i<=n;i++){
		fact[i]=fact[i-1]*i%mod;
		invfact[i]=invfact[i-1]*inv(i)%mod;
	}
}
void solve(){
	int n,k;
	scanf("%d %d",&n,&k);
	init(n);
	for(int i=0;i<=n;i++){
		sum[i]=0;
	}
	while(k--){
		int l,r;
		scanf("%d %d",&l,&r);
		unsigned long long v=rnd();
		sum[l]^=v;
		sum[r+1]^=v;
	}
	map<unsigned long long,int> dict;
	for(int i=1;i<=n;i++){
		sum[i]^=sum[i-1];
		dict[sum[i]]++;
	}
	long long ans=1;
	for(map<unsigned long long,int> :: iterator iter=dict.begin();iter!=dict.end();iter++){
		long long pre;
		if(iter->second%2==0){
			pre=((fact[iter->second]*invfact[iter->second/2]%mod*invfact[iter->second/2]%mod-fact[iter->second]*invfact[iter->second/2-1]%mod*invfact[iter->second/2+1]%mod)%mod+mod)%mod;
		}
		else{
			pre=0;
		}
		ans=ans*pre%mod;
	}
	printf("%lld\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		solve();
	} 
	return 0;
}