AtCoder Beginner Contest 453 E,F,G問題メモ

def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, constraints):
    MOD = 998244353

    aaa = [0] * (n + 2)
    bbb = [0] * (n + 2)
    both = [0] * (n + 2)
    for l, r in constraints:
        ai = l
        bi = n - r
        ci = min(r + 1, n - l + 1)
        if ai == bi:
            both[ai] += 1
        elif ai < bi:
            aaa[ai] += 1
            if bi < ci:
                aaa[bi] -= 1
                both[bi] += 1
            else:
                aaa[ci] -= 1
        else:
            bbb[bi] += 1
            if ai < ci:
                bbb[ai] -= 1
                both[ai] += 1
            else:
                bbb[ci] -= 1
    for i in range(1, n + 1):
        aaa[i + 1] += aaa[i]
        bbb[i + 1] += bbb[i]
        both[i + 1] += both[i]

    facts, finvs = precompute_factorials(n, MOD)

    def ncr(n, r):
        return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD

    ans = 0
    for a in range(1, n // 2 + 1):
        b = n - a
        fix_a = aaa[a]
        fix_b = bbb[a]
        both_ok = both[a]
        if fix_a + fix_b + both_ok < n:
            continue
        if a < fix_a or b < fix_b:
            continue
        if a == b:
            ans += ncr(both_ok, a - fix_a)
        else:
            ans += ncr(both_ok, a - fix_a) * 2
        ans %= MOD
    return ans


n = int(input())
constraints = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, constraints)
print(ans)

from collections import deque

from collections import defaultdict


def get_centroid(n: int, links: list[list[int]], s: int, removed: set[int] | None = None) \
        -> tuple[list[int], dict[int, int]]:
    """
    ※===葉に1、他に0の重みを付けた重心に改造。s は葉でない頂点が指定される前提。===

    木の重心を見つける。
    重心は1つまたは2つあるため、リストで返す。また、s を根とした際の部分木のサイズも返す。

    繰り返し重心分解する場合にも適用可能。
    removedには既に重心として確定された頂点集合を与え、そこにある頂点は探索されないようになる。
    n には木全体ではなく、探索範囲の頂点数を与える。（1回前に探索した部分木のサイズから計算できる）

    :param n: 木の（探索範囲の）頂点数
    :param links: 隣接リスト
    :param s: 探索開始頂点
    :param removed: 探索しない頂点集合
    :return:
    """
    if removed is None:
        removed = set()

    leaf_count = sum(len(links[i]) == 1 for i in range(n))

    parents = {s: -1}
    subtree_sizes = {s: leaf_count}
    status = defaultdict(int)
    q = [s]
    limit = leaf_count // 2
    centroid = []
    while q:
        u = q[-1]
        if status[u] == 0:
            status[u] = 1
            for v in links[u]:
                if parents[u] == v:
                    continue
                if v in removed:
                    continue
                parents[v] = u
                q.append(v)
        else:
            status[u] = 2
            q.pop()
            my = 1 if len(links[u]) == 1 else 0
            is_centroid = True
            for v in links[u]:
                if status[v] != 2:
                    continue
                if v in removed:
                    continue
                scv = subtree_sizes[v]
                my += scv
                if scv > limit:
                    is_centroid = False
            subtree_sizes[u] = my
            if leaf_count - my > limit:
                is_centroid = False
            if is_centroid:
                centroid.append(u)
    return centroid, subtree_sizes


def solve(n, k, edges, ccc):
    if n == 2:
        for col, cnt in enumerate(ccc, start=1):
            if cnt >= 2:
                return [col, col]
        return [-1]

    links = [[] for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].append(v)
        links[v].append(u)

    s = next(i for i in range(n) if len(links[i]) >= 2)
    centroid, sizes = get_centroid(n, links, s)
    c1 = centroid[0]

    leafs = []  # 重み付き重心 c1 を根とした DFS における訪問順の葉
    q = [c1]
    queued = [False] * n
    queued[c1] = True
    while q:
        u = q.pop()
        if len(links[u]) == 1:
            leafs.append(u)
        for v in links[u]:
            if not queued[v]:
                queued[v] = True
                q.append(v)

    colors_two_cnt = []
    colors_two_val = []
    colors_one = []
    for col, cnt in enumerate(ccc, start=1):
        if cnt == 1:
            colors_one.append(col)
        else:
            colors_two_val.append(col)
            colors_two_cnt.append(cnt)

    m = len(leafs)
    if m > sum(colors_two_cnt):
        return [-1]

    ans = [-1] * n
    ci = 0
    half = (m + 1) // 2
    order = [x for pair in zip(range(half), range(half, m)) for x in pair]
    if m % 2:
        order.append(half - 1)

    def put_color(i):
        nonlocal ci
        ans[i] = colors_two_val[ci]
        colors_two_cnt[ci] -= 1
        if colors_two_cnt[ci] == 0:
            ci += 1

    for i in order:
        put_color(leafs[i])

    colors_two_val.extend(colors_one)
    colors_two_cnt.extend([1] * len(colors_one))
    if ans[c1] == -1:
        put_color(c1)
    for v in range(n):
        if ans[v] == -1:
            put_color(v)

    return ans


t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    edges = [list(map(int, input().split())) for _ in range(n - 1)]
    ccc = list(map(int, input().split()))
    ans = solve(n, k, edges, ccc)
    print(*ans)

from operator import add

from atcoder.segtree import SegTree


def solve(n, m, q, queries):
    refs = [0] * n
    query_for_state = [[] for _ in range(q + 1)]
    state_children = [[] for _ in range(q + 1)]
    state_parents = [-1] * (q + 1)
    for qi, query in enumerate(queries, start=1):
        if query[0] == 1:
            _, x, y = query
            x -= 1
            y -= 1
            refs[x] = refs[y]
        elif query[0] == 2:
            _, x, y, z = query
            x -= 1
            y -= 1
            rx = refs[x]
            state_children[rx].append(qi)
            state_parents[qi] = rx
            refs[x] = qi
        else:
            _, x, l, r = query
            x -= 1
            l -= 1
            rx = refs[x]
            query_for_state[rx].append((qi, l, r))

    sgt = SegTree(add, 0, m)
    progress = [0] * (q + 1)
    state_changes = [(0, 0)]
    ans = [-1] * (q + 1)
    st = 0
    while st != -1:
        if progress[st] == 0:
            for qi, l, r in query_for_state[st]:
                ans[qi] = sgt.prod(l, r)
        if progress[st] == len(state_children[st]):
            y, z0 = state_changes.pop()
            sgt.set(y, z0)
            st = state_parents[st]
            continue
        st_ = state_children[st][progress[st]]
        progress[st] += 1
        st = st_
        y = queries[st - 1][2] - 1
        z = queries[st - 1][3]
        state_changes.append((y, sgt.get(y)))
        sgt.set(y, z)

    ans = [a for a in ans if a != -1]
    return ans


n, m, q = map(int, input().split())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, m, q, queries)
print('\n'.join(map(str, ans)))