考虑到区间的限制 \([l, r]\) 就是要求 \([l, r]\) 里的字符会在 \([l, r]\) 里找到匹配。
假设还有个区间 \([l', r']\) 满足 \(l\le l'\le r\le r'\)，能够发现限制变成了 \([l, l'), [l', r], (r, r']\) 这 \(3\) 个区间内的字符能在对应区间内找到匹配。
继续，假设 \(l\le l'\le r'\le r\)，此时能发现是 \([l', r']\) 内的字符可以在这个区间里找到匹配，同时对于 \([l, l')\cup (r', r]\) 内的字符可以在这个集合中找到匹配。
于是可以想到用把覆盖其的区间相同的点划分到一个等价类中，一个等价类中的点就要求需要互相匹配。
对于互相匹配的方案数，设等价类中点个数为 \(p\)，就相当于是求长度为 \(p\) 的合法括号序列的数量。
方案数就为 \(\operatorname{Catalan}(\frac{p}{2})\)，当 \(p\bmod 2 = 1\) 时无解。
对于划分等价类，可以考虑 \(\text{xor-hash}\)。
具体来说，令点权为 \(a_i\)，对于每个区间 \([l, r]\) 赋上一个权值 \(val\)，就对 \(i\in [l, r]\) 进行 \(a_i\leftarrow a_i\oplus val\)，这个是可以差分处理的。
正确性显然，不被相同的线段所覆盖的点肯定一个点相对于另一个点会多或者少 \(\oplus\) 一些线段的权值，权值就不会相同。
冲突的概率为 \(2^{-w}\) 次方的，采用 \(64\) 位碰撞的概率极小。
时间复杂度 \(O(n\log n)\)。
代码
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
const i64 mod = 998244353;
inline i64 qpow(i64 a, i64 b) {i64 v = 1; while (b) b & 1 && ((v *= a) %= mod), (a *= a) %= mod, b >>= 1; return v;}
const int maxn = 3e5 + 10, limn = 3e5;
i64 fac[maxn], invf[maxn];
inline i64 C(int n, int m) {return fac[n] * invf[m] % mod * invf[n - m] % mod;}
inline i64 Catalan(int n) {return n & 1 ? 0 : ((C(n, n / 2) - C(n, n / 2 - 1) + mod) % mod);}
inline void init() {
fac[0] = 1;
for (int i = 1; i <= limn; i++) fac[i] = fac[i - 1] * i % mod;
invf[limn] = qpow(fac[limn], mod - 2);
for (int i = limn; i; i--) invf[i - 1] = invf[i] * i % mod;
}
u64 val[maxn];
inline void Main() {
std::mt19937_64 Rand(std::chrono::steady_clock::time_point().time_since_epoch().count());
int n, k; scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) val[i] = 0;
while (k--) {
int l, r; scanf("%d%d", &l, &r);
u64 v = Rand();
val[l] ^= v, val[r + 1] ^= v;
}
for (int i = 1; i <= n; i++) val[i] ^= val[i - 1];
std::sort(val + 1, val + n + 1);
i64 ans = 1;
for (int i = 1, j; i <= n; i = j) {
for (j = i; j <= n && val[i] == val[j]; j++);
(ans *= Catalan(j - i)) %= mod;
}
printf("%lld\n", ans);
}
int main() {
init();
int T; scanf("%d", &T);
while (T--) Main();
return 0;
}