Hyperregular Bracket Strings (Codeforces 1831E)
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):
import os, sys
from io import BytesIO, IOBase
from typing import *
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
MOD = 998244353

def singleton(__init__):

    def __new__(cls, *args, **kwargs):
        if hasattr(cls, 'instance'):
            return getattr(cls, 'instance')
        instance = super(cls, cls).__new__(cls)
        __init__(instance, *args, **kwargs)
        setattr(cls, 'instance', instance)
        return instance
    return __new__

class Inverse:

    @singleton
    def __new__(cls):
        cls.inverse = {1: 1}

    def __getitem__(self, item):
        for i in range(len(self.inverse) + 1, item + 1):
            self.inverse[i] = self.inverse[MOD % i] * (MOD - MOD // i) % MOD
        return self.inverse[item]

class Catalan:

    @singleton
    def __new__(cls):
        cls.catalan = [1]

    def __getitem__(self, item):
        for i in range(len(self.catalan), item + 1):
            self.catalan.append(self.catalan[-1] * (4 * i - 2) * Inverse()[i + 1] % MOD)
        return self.catalan[item]

def main():
    (n, k) = map(int, input().split())
    (diff, bit) = ([0] * (n + 1), 1)
    mod1 = 1000000007
    for _ in range(k):
        (left, right) = map(int, input().split())
        diff[left - 1] = diff[left - 1] + bit
        diff[right] = diff[right] - bit
        bit = bit * mod1 % MOD
    diff.pop()
    for i in range(1, n):
        diff[i] += diff[i - 1]
    result = 1
    for count in Counter(diff).values():
        if count & 1:
            return 0
        result = result * Catalan()[count >> 1] % MOD
    return result
if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        print(main())

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, deque, defaultdict
from functools import lru_cache
from math import factorial, sqrt, gcd, log2
from math import lcm
from copy import deepcopy
import heapq
from random import shuffle, randint
from sys import stdin, stdout
input = stdin.readline

def main():
    MOD = 998244353
    n = 6 * 10 ** 5
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    inverse = [0] * (n + 1)
    inverse[n] = pow(fact[n], MOD - 2, MOD)
    for i in range(n, 0, -1):
        inverse[i - 1] = inverse[i] * i % MOD

    def comb(n: int, m: int, MOD) -> int:
        if m < 0 or m > n:
            return 0
        return fact[n] * inverse[m] % MOD * inverse[n - m] % MOD
    t = int(input())
    for _ in range(t):
        (n, k) = map(int, input().split())
        cha_L = [0] * (n + 10)
        cha2_L = [0] * (n + 10)
        for i in range(k):
            (left, right) = map(int, input().split())
            left -= 1
            right -= 1
            rd = randint(1, 10 ** 7)
            cha_L[left] ^= rd
            cha_L[right + 1] ^= rd
            rd2 = randint(1, 10 ** 7)
            cha2_L[left] ^= rd2
            cha2_L[right + 1] ^= rd2
        if n % 2 != 0:
            print(0)
            continue
        dic = Counter()
        cur1 = 0
        cur2 = 0
        for i in range(n):
            num1 = cha_L[i]
            num2 = cha2_L[i]
            cur1 ^= num1
            cur2 ^= num2
            dic[cur1, cur2] += 1
        ans = 1
        for (num, count) in dic.items():
            if count % 2 == 1:
                print(0)
                break
            else:
                count = count // 2
                ans = ans * (comb(2 * count, count, MOD) - comb(2 * count, count - 1, MOD)) % MOD
        else:
            print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import collections
MOD = 998244353

def get_catalan():
    catalan = [1]
    inverse = [None, 1]

    def inner(n):
        for i in range(len(inverse), n + 2):
            inverse.append(inverse[MOD % i] * (MOD - MOD // i) % MOD)
        for i in range(len(catalan), n + 1):
            catalan.append(catalan[-1] * (4 * i - 2) * inverse[i + 1] % MOD)
        return catalan[n]
    return inner

def testcase():
    (n, k) = map(int, input().split())
    (prefix_sum, bit) = ([0] * (n + 1), 1)
    for _ in range(k):
        (l, r) = map(int, input().split())
        prefix_sum[l - 1] = prefix_sum[l - 1] + bit
        prefix_sum[r] = prefix_sum[r] - bit
        bit = bit * 1000000007 % MOD
    prefix_sum.pop()
    for i in range(1, n):
        prefix_sum[i] = prefix_sum[i] + prefix_sum[i - 1]
    result = 1
    catalan = get_catalan()
    for count in collections.Counter(prefix_sum).values():
        if count & 1:
            return print(0)
        result = result * catalan(count >> 1) % MOD
    print(result)
if __name__ == '__main__':
    for _ in range(int(input())):
        testcase()