Hyperregular Bracket Strings (Codeforces 1830C)
Tags: Math, hashing

You are given an integer $$$n$$$ and $$$k$$$ intervals. The $$$i$$$-th interval is $$$[l_i,r_i]$$$ where $$$1 \leq l_i \leq r_i \leq n$$$.Let us call a regular bracket sequence$$$^{\dagger,\ddagger}$$$ of length $$$n$$$ hyperregular if for each $$$i$$$ such that $$$1 \leq i \leq k$$$, the substring $$$\overline{s_{l_i} s_{l_{i}+1} \ldots s_{r_i}}$$$ is also a regular bracket sequence.Your task is to count the number of hyperregular bracket sequences. Since this number can be really large, you are only required to find it modulo $$$998\,244\,353$$$.$$$^\dagger$$$ A bracket sequence is a string containing only the characters "(" and ")".$$$^\ddagger$$$ A bracket sequence is called regular if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), (()(())) and the empty string are regular, while )(, ((), and (()))( are not.

Input: Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$0 \le k \le 3 \cdot 10^5$$$) — the length of the hyperregular bracket sequences and the number of intervals respectively.The following $$$k$$$ lines of each test case contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l \le r \le n$$$).It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$ and the sum of $$$k$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, output the number of hyperregular bracket sequences modulo $$$998\,244\,353$$$.

Note:   For the first testcase, the $$$5$$$ hyperregular bracket strings of length $$$6$$$ are: ((())), (()()), (())(), ()(()) and ()()(). For the second testcase, there are no regular bracket strings of length $$$5$$$, and consequently, there are no hyperregular bracket strings of length $$$5$$$. For the third testcase, there are no hyperregular bracket strings of length $$$8$$$ for which the substring $$$[1 \ldots 3]$$$ is a regular bracket string. For the fourth testcase, there $$$4$$$ hyperregular bracket strings are: ((())(())), ((())()()), ()()((())) and ()()(()()) 

Sample Inputs:
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

Sample Outputs:
5
0
0
4
839415253
140
2

Solution (Python):
mod = 998244353
table_size = 3 * 10 ** 5 + 10
fac = [1] * (table_size + 1)
finv = [1] * (table_size + 1)
for i in range(2, table_size + 1):
    fac[i] = fac[i - 1] * i % mod
finv[table_size] = pow(fac[table_size], mod - 2, mod)
for i in range(table_size - 1, -1, -1):
    finv[i] = finv[i + 1] * (i + 1) % mod

def rebuild(n):
    global table_size, fac, finv
    fac += [0] * (n - table_size)
    fac += [0] * (n - table_size)
    finv += [0] * (n - table_size)
    for i in range(table_size + 1, n + 1):
        fac[i] = fac[i - 1] * i % mod
    finv[n] = inv(fac[n])
    for i in range(n - 1, table_size, -1):
        finv[i] = finv[i + 1] * (i + 1) % mod
    table_size = n

def binom(n, k):
    if n < 0 or k < 0:
        return 0
    if k > n:
        return 0
    if n > table_size:
        rebuild(n + 10 ** 4)
    return fac[n] * finv[k] % mod * finv[n - k] % mod

def fpow(x, k):
    res = 1
    while k:
        if k & 1:
            res = res * x % mod
        x = x * x % mod
        k >>= 1
    return res

def inv(a):
    if a < table_size:
        return fac[a - 1] * finv[a] % mod
    return fpow(a, mod - 2)
from sys import stdin
input = lambda : stdin.readline()[:-1]
import random
import collections

def solve():
    (n, q) = map(int, input().split())
    LR = [0] * (n + 1)
    for _ in range(q):
        (l, r) = map(lambda x: int(x) - 1, input().split())
        h = random.randint(1, 1 << 62)
        LR[l] ^= h
        LR[r + 1] ^= h
    for i in range(n):
        LR[i + 1] ^= LR[i]
    d = collections.Counter(LR[:-1])
    ans = 1
    for v in d.values():
        if v % 2:
            print(0)
            return
        ans *= binom(v, v // 2) * inv(v // 2 + 1) % mod
        ans %= mod
    print(ans)
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
import random
cmbMOD = 998244353
cmbN = 3 * 10 ** 5 + 10
cmbfact = [1, 1]
cmbfactinv = [1, 1]
cmbinv = [0, 1]
for i in range(2, cmbN + 1):
    cmbfact.append(cmbfact[-1] * i % cmbMOD)
    cmbinv.append(-cmbinv[cmbMOD % i] * (cmbMOD // i) % cmbMOD)
    cmbfactinv.append(cmbfactinv[-1] * cmbinv[-1] % cmbMOD)

def cmb(n, r):
    if n < r:
        return 0
    else:
        return cmbfact[n] * cmbfactinv[r] * cmbfactinv[n - r] % cmbMOD
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    f = False
    flag = [0] * n
    cnt = [0] * (n + 1)
    flag[0] = 1
    flag[-1] = -1
    for _ in range(k):
        (l, r) = map(int, input().split())
        l -= 1
        r -= 1
        if flag[l] == -1:
            f = True
        flag[l] = 1
        rd = random.randint(1000000000, 9999999999)
        cnt[l] ^= rd
        if flag[r] == 1:
            f = True
        flag[r] = -1
        cnt[r + 1] ^= rd
    if n % 2:
        print(0)
        continue
    for i in range(1, n):
        cnt[i] ^= cnt[i - 1]
    from collections import Counter
    c = Counter(cnt[:-1])
    ans = 1
    for v in c.values():
        if v % 2:
            f = True
            break
        ans *= cmb(v, v // 2) * cmbinv[v // 2 + 1] % cmbMOD
        ans %= cmbMOD
    if f:
        print(0)
    else:
        print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from random import randrange
from collections import defaultdict
MAXN = 6 * 10 ** 5 + 1
MOD = 998244353
fac = [1] * MAXN
ifac = [0] * MAXN
for i in range(2, MAXN):
    fac[i] = fac[i - 1] * i % MOD
ifac[MAXN - 1] = pow(fac[MAXN - 1], -1, MOD)
for i in range(MAXN - 2, -1, -1):
    ifac[i] = ifac[i + 1] * (i + 1) % MOD

def rbs(n):
    return 0 if n & 1 else fac[n] * (ifac[n // 2] ** 2 % MOD) % MOD * pow(n // 2 + 1, -1, MOD) % MOD
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    events = [[] for _ in range(n + 2)]
    for seg in range(k):
        (l, r) = map(int, input().split())
        x = randrange(1 << 60)
        events[l].append(x)
        events[r + 1].append(x)
    length = defaultdict(int)
    active_hash = 0
    for i in range(1, n + 1):
        for x in events[i]:
            active_hash ^= x
        length[active_hash] += 1
    ans = 1
    for x in length.values():
        ans = ans * rbs(x) % MOD
    print(ans)