C. 超正则括号序列 详细题解

问题重述

给定长度 $n$ 和 $k$ 个区间 $[l_i, r_i]$。统计长度为 $n$ 的括号序列的数量，满足：

1. 整个序列是正则括号序列（RBS）
2. 每个区间对应的子串也是正则括号序列

答案对 $998244353$ 取模。

前置知识

正则括号序列的判定

对于括号序列 $s_1 s_2 \dots s_k$，定义：

$$f(s_i) = \begin{cases} 1, & \text{if } s_i = \text{'('} \\ -1, & \text{if } s_i = \text{')'} \end{cases} $$$$\Delta_i = \sum_{j=1}^{i} f(s_j)$$

序列是正则括号序列当且仅当：

1. $\Delta_k = 0$（总括号数平衡）
2. $\Delta_i \ge 0$ 对所有 $1 \le i \le k$（前缀和非负）

卡特兰数

长度为 $2m$ 的正则括号序列的数量为第 $m$ 个卡特兰数：

$$C_m = \frac{1}{m+1} \binom{2m}{m}$$

关键观察

观察 1：分组思想

如果一个位置被某些区间覆盖，这些区间要求该位置必须与其对应位置匹配。实际上，所有被完全相同的一组区间覆盖的位置属于同一个组。

观察 2：组内独立性

不同组之间是独立的：一个组内的括号选择不影响其他组。因此：

$$\text{总方案数} = \prod_{\text{每个组}} C_{\text{组大小}/2}$$

其中组大小必须是偶数，否则方案数为 $0$。

观察 3：区间覆盖集合的表示

使用异或哈希（XOR hashing）来标识每个位置被哪些区间覆盖：

• 为每个区间 $[l, r]$ 随机生成一个 64 位哈希值 $h$
• 在差分数组上：$diff[l] \oplus= h$，$diff[r+1] \oplus= h$
• 计算前缀异或得到每个位置的哈希值
• 哈希值相同的点属于同一组

算法步骤

1. 预处理卡特兰数：计算所有 $C_{2i}$ 模 $998244353$ 的值

2. 处理每个测试用例：

   • 添加区间 $[1, n]$（整个序列必须是 RBS）
   • 为每个区间随机生成哈希值，更新差分数组
   • 计算前缀异或，统计每个哈希值对应的长度
   • 对每个组，如果长度为奇数，答案为 $0$
   • 否则答案乘以 $C_{\text{len}/2}$

时间复杂度

• 预处理卡特兰数：$O(N_{\max})$
• 每个测试用例：$O(k \log k)$（由于排序或 map 操作）
• 总复杂度：$O((n+k) \log (n+k))$

完整代码

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

typedef long long ll;
const int NMAX = 300005;
const int MOD = 998244353;

// 随机数生成器
mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> rnd(0, LLONG_MAX);

// 阶乘和逆元
ll fact[NMAX], invfact[NMAX], C[NMAX];

// 快速幂
ll binPow(ll x, ll y) {
    ll ans = 1;
    for (; y; y >>= 1, x = x * x % MOD) {
        if (y & 1) ans = ans * x % MOD;
    }
    return ans;
}

// 添加区间，使用异或哈希
map<ll, ll> diff, freq;

void add_interval(ll l, ll r) {
    ll Hash = rnd(gen);
    diff[l] ^= Hash;
    diff[r + 1] ^= Hash;
}

void solve() {
    ll n, k;
    cin >> n >> k;
    
    diff.clear();
    freq.clear();
    
    // 整个序列必须是 RBS
    add_interval(1, n);
    
    // 添加所有给定区间
    for (ll i = 0; i < k; i++) {
        ll l, r;
        cin >> l >> r;
        add_interval(l, r);
    }
    
    // 计算前缀异或，统计每个哈希值的总长度
    ll Hash = diff[1];
    for (auto it = next(diff.begin()); it != diff.end(); it++) {
        freq[Hash] += it->first - prev(it)->first;
        Hash ^= it->second;
    }
    
    // 计算答案
    ll ans = 1;
    for (const auto& [h, len] : freq) {
        if (len % 2 == 1) {
            ans = 0;
            break;
        }
        ans = ans * C[len] % MOD;
    }
    
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    // 预处理阶乘和逆元
    fact[0] = invfact[0] = 1;
    for (ll i = 1; i < NMAX; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        invfact[i] = binPow(fact[i], MOD - 2);
    }
    
    // 预处理卡特兰数：C[2m] = C_m
    for (ll i = 0; i * 2 < NMAX; i++) {
        C[i * 2] = fact[i * 2] * invfact[i] % MOD * invfact[i + 1] % MOD;
    }
    
    ll t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

代码说明

1. 异或哈希：

   • 每个区间随机生成一个 64 位哈希值
   • 使用差分数组 $diff$ 记录哈希值的变化
   • 前缀异或得到每个位置的哈希值

2. 分组统计：

   • 遍历差分数组，计算每个哈希值对应的连续段长度
   • 哈希值相同的位置属于同一组

3. 答案计算：

   • 如果某组长度为奇数，无法形成合法括号序列，答案为 $0$
   • 否则，该组的方案数为 $C_{\text{len}/2}$（卡特兰数）

4. 模运算：

   • 使用费马小定理计算逆元：$a^{-1} \equiv a^{MOD-2} \pmod{MOD}$

示例验证

以第一个测试用例 n=6, k=0 为例：

• 只有区间 $[1,6]$
• 所有位置哈希值相同，组成一个大小为 $6$ 的组
• 方案数 = $C_3 = 5$，与输出一致

总结

本题的核心技巧：

1. 使用异或哈希将区间覆盖问题转化为分组问题
2. 利用卡特兰数计算每组内的方案数
3. 通过随机化避免哈希冲突（冲突概率极低）
4. 差分数组实现 $O(n+k)$ 的哈希值计算