题解：CF1830C Hyperregular Bracket Strings

· · 题解

题意

给定一个长度 n 和 k 个区间 [l_i, r_i]，要求计算有多少个长度为 n 的合法括号序列，使得每个区间内的子串也是合法括号序列。

分析

这题的核心是要处理多个区间约束下的括号序列计数。直接考虑所有约束非常复杂，我们需要找到一个方法将这些约束"拆分"成独立的部分。

关键观察：如果两个位置被完全相同的区间集合覆盖，那么它们必须属于同一个连续的括号序列段。

我们可以用随机哈希来标记每个位置被哪些区间覆盖：

  1. 给每个区间 [l_i, r_i] 分配一个随机 64 位哈希值
  2. 用差分在 l_i 处异或这个值，在 r_i+1 处再次异或
  3. 计算前缀异或，每个位置的最终值就是覆盖它的所有区间的哈希和

这样，哈希值相同的位置就被相同的区间集合覆盖，必须形成连续段。

把序列按哈希值分成若干连续段后，每个段必须是合法括号序列。设段长为 len：

总方案数就是所有段方案数的乘积。

::::info[卡特兰数计算]

使用组合数差公式，避免除法取模：

Cat(m) = C_{2m}^m - C_{2m}^{m-1}

预处理阶乘和逆元可以 O(1) 计算组合数。 ::::

Code

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

const int N=1e6+5;
const ll mod=998244353;

map<ull,int> cnt;        // 统计每种哈希值的连续长度
ll fac[N],inv[N];        // 阶乘和逆元
ull a[N];                // 差分数组
mt19937_64 rng(20090207);// 64位随机数生成器

// 快速幂
ll qpow(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod; y>>=1;
    }
    return res;
}

// 预处理阶乘逆元
void init(){
    fac[0]=1;
    for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
    inv[N-1]=qpow(fac[N-1],mod-2);
    for(int i=N-1;i>0;i--)
        inv[i-1]=inv[i]*i%mod;
}

// 组合数
ll C(ll n,ll m){
    if(n<0||m<0||m>n)return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

// 卡特兰数
ll catalan(int x){
    if(x&1)return 0;           // 奇数长度不可能
    if(x==0)return 1;          // 空序列算一种
    int m=x/2;
    return (C(2*m,m)-C(2*m,m-1)+mod)%mod;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    init();
    int T; cin>>T;
    while(T--){
        int n,k; cin>>n>>k;
        cnt.clear();

        // 差分标记
        for(int i=1;i<=k;i++){
            int l,r; cin>>l>>r;
            ull val=rng();     // 给区间分配随机哈希值
            a[l]^=val;
            a[r+1]^=val;
        }

        // 前缀异或得到每个位置的哈希值
        for(int i=1;i<=n;i++){
            a[i]^=a[i-1];
            cnt[a[i]]++;
        }

        // 清空数组
        for(int i=1;i<=n+1;i++)a[i]=0;

        // 计算答案
        ll ans=1;
        for(auto &[h,len]:cnt)
            ans=ans*catalan(len)%mod;

        cout<<ans<<"\n";
    }
    return 0;
}