题目描述

难度分:$2400$

输入$T(\leq 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 3 \times 10^5$，$k$之和$\leq 3 \times 10^5$。

每组数据输入$n(1 \leq n \leq 3 \times 10^5)$，$k(0 \leq k \leq 3 \times 10^5)$和$k$个闭区间 $[l_i,r_i]$，区间端点均在$[1,n]$内。

输出有多少个长为$n$的合法括号字符串$s$，满足$s$的每个子串$[l_i,r_i]$也是合法括号字符串。

考虑到答案可能很大，对其模$998244353$后再输出。

输入样例

7
6 0
5 0
8 1
1 3
10 2
3 4
6 9
1000 3
100 701
200 801
300 901
28 5
1 12
3 20
11 14
4 9
18 19
4 3
1 4
1 4
1 4

输出样例

5
0
0
4
839415253
140
2

算法

差分数组+组合数学

今天这道题的随机异或技巧我真是第一次见，首先有个前置结论：长度为$2n$的括号序列有$C_{2n}^{n}$个（即卡特兰数）。下面分类讨论一下：

1. 如果$k=1$，那么区间$[l_1,r_1]$为合法括号序列的方案有$a=C_{r_1-l_1+1}^{[\frac{r_1-l_1+1}{2}]}$种，其中$[.]$表示对$.$向下取整。而剩下的部分拼起来也必须要是合法的括号序列，假设剩下的长度为$len=n-(r_1-l_1+1)$，答案就是$b=C_{len}^{[\frac{len}{2}]}$，最终答案就是$a \times b$。

2. 如果$k \gt 1$，如法炮制，但是需要注意如果两个区间$[l_1,r_1]$和$[l_2,r_2]$相交，比如$[l_1,r_1] \in [l_2,r_2]$，约束就会被分成三段$[l_2,l_1]$、$[l_1,r_1]$、$[r_1,r_2]$。需要分别计算三段的卡特兰数，三者乘起来才是整体的答案。再比如，若$l_2 \in [l_1,r_1]$且$r_2 \gt r_1$，约束就会被分为$[l_1,l_2]$、$[l_2，r_1]$、$[r_1,r_2]$三段。

所以我们遍历所有区间$[l_i,r_i]$，只要能确定最终被分裂成了多少个区间，就能确定最终的方案数。问题就在于如何确定哪些区间是可以拼在一起考虑的，对于某个区间$[l_i,r_i]$，可以在这个区间上异或上一个随机数，操作差分数组$d$就只需要操作$l_i$和$r_i+1$两个端点。遍历完所有区间后求$d$的前缀异或和，就能得到结果，异或值相同的位置就可以连接起来形成一个合法的括号串。

接下来用哈希表对$[1,n]$上的异或值分组，异或值为$eor_i$的位置个数$cnt_i$就是该值拼出来的合法括号长度。把所有的$C_{cnt_i}^{[\frac{cnt_i}{2}]}$乘起来就是答案。

复杂度分析

时间复杂度

遍历每个区间$[l_i,r_i]$时对差分数组$d$上异或一个数的时间复杂度为$O(1)$，因此$k$个区间的时间复杂度为$O(k)$。接下来对$d$求前缀和，并得到哈希表分组结果的时间复杂度为$O(n)$。哈希表在最差情况下有$O(n)$个键值对（几乎每个位置的异或值都不同），所以遍历哈希表计算最终答案的时间复杂度也为$O(n)$。算法整体的时间复杂度为$O(k+n)$。

空间复杂度

空间消耗在于哈希表和差分数组$d$，它们消耗的空间都是线性的，因此算法的额外空间复杂度为$O(n)$。

C++ 代码

#include<bits/stdc++.h>

using LL = long long;
using u64 = unsigned long long;
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int N = 300010, MOD = 998244353;
int t, n, k;
LL h[N];

int fast_power(int a, int b) {
    int res = 1;
    while(b) {
        if(b&1) res = (LL)res*a%MOD;
        a = (LL)a*a%MOD;
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return fast_power(x, MOD - 2);
}

void init() {
    h[0] = 1;
    for(int i = 1; i <= N - 10; i++) {
        h[i] = h[i - 1]*(4LL*i%MOD - 2 + MOD)%MOD*inv(i + 1)%MOD;
    }
}

int main() {
    if(h[0] == 0) init();
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &k);
        std::vector<u64> d(n + 10);
        for(int i = 0; i < k; i++) {
            int l, r;
            scanf("%d%d", &l, &r);
            auto x = rng();
            d[l] ^= x;
            d[r + 1] ^= x;
        }
        for(int i = 1; i <= n; i++) {
            d[i] ^= d[i - 1];
        }
        std::map<u64, int> cnt;
        for(int i = 1; i <= n; i++) {
            cnt[d[i]]++;
        }
        int ans = 1;
        for(auto&[_, x]: cnt) {
            if(x&1) {
                ans = 0;     // 奇数长度不可能构成合法括号串
            }else {
                ans = (LL)ans*h[x>>1]%MOD;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}