#1181717 (PyPy3) No.3785 Tree of Multiples

• 問題: No.3785 Tree of Multiples
• ユーザー: askr58
• 提出日時: 2026-08-31 08:22:07
• 言語: PyPy3 (8.0.0 + ACL)
• 結果: AC
• 実行時間: 2,740 ms / 6,000 ms
• コード長: 5,367 bytes
• コンパイル時間: 84 ms
• コンパイル使用メモリ: 64,560 KB
• 実行使用メモリ: 121,972 KB
• 最終ジャッジ日時: 2026-10-30 20:55:02
• 合計ジャッジ時間: 16,845 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge7_0

ファイルパターン	結果
sample	AC * 3
other	AC * 16

ソースコード

#generated by ChatGPT
import sys
from heapq import heappush, heappop

MOD = 998244353
PRIMITIVE_ROOT = 3
MAX_LOG = 23

# 長さ 2^k の NTT で使う原始 2^k 乗根。
ROOT = [1] * (MAX_LOG + 1)
IROOT = [1] * (MAX_LOG + 1)
for k in range(1, MAX_LOG + 1):
    ROOT[k] = pow(PRIMITIVE_ROOT, (MOD - 1) >> k, MOD)
    IROOT[k] = pow(ROOT[k], MOD - 2, MOD)

# 小さい多項式同士では NTT より素朴畳み込みの方が軽い。
NAIVE_LIMIT = 4096


def ntt(a, inverse=False):
    """a を in-place で NTT / 逆 NTT する。長さは 2 の冪。"""
    n = len(a)

    # bit reversal
    j = 0
    for i in range(1, n):
        bit = n >> 1
        while j & bit:
            j ^= bit
            bit >>= 1
        j ^= bit
        if i < j:
            a[i], a[j] = a[j], a[i]

    length = 2
    level = 1
    roots = IROOT if inverse else ROOT

    while length <= n:
        half = length >> 1
        wlen = roots[level]

        for left in range(0, n, length):
            w = 1
            right = left + half
            for i in range(left, right):
                u = a[i]
                v = a[i + half] * w % MOD

                x = u + v
                if x >= MOD:
                    x -= MOD
                y = u - v
                if y < 0:
                    y += MOD

                a[i] = x
                a[i + half] = y
                w = w * wlen % MOD

        length <<= 1
        level += 1

    if inverse:
        inv_n = pow(n, MOD - 2, MOD)
        for i in range(n):
            a[i] = a[i] * inv_n % MOD


def merge_pair(f1, h1, f2, h2):
    """
    (F1, H1), (F2, H2) から
        F = F1 F2
        H = H1 F2 + F1 H2
    を作る。
    """
    n1 = len(f1)
    n2 = len(f2)
    need = n1 + n2 - 1

    if n1 * n2 <= NAIVE_LIMIT:
        f = [0] * need
        h = [0] * need

        for i in range(n1):
            fi = f1[i]
            hi = h1[i]
            for j in range(n2):
                k = i + j
                f[k] += fi * f2[j]
                h[k] += hi * f2[j] + fi * h2[j]

        for i in range(need):
            f[i] %= MOD
            h[i] %= MOD
        return f, h

    size = 1 << (need - 1).bit_length()

    a = f1 + [0] * (size - n1)
    b = h1 + [0] * (size - n1)
    c = f2 + [0] * (size - n2)
    d = h2 + [0] * (size - n2)

    # 同じ変換を使い回す。
    ntt(a)
    ntt(b)
    ntt(c)
    ntt(d)

    f = [0] * size
    h = [0] * size

    for i in range(size):
        f[i] = a[i] * c[i] % MOD
        h[i] = (b[i] * c[i] + a[i] * d[i]) % MOD

    ntt(f, True)
    ntt(h, True)

    del f[need:]
    del h[need:]
    return f, h


def solve():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())

    A = {}
    B = {}
    nA = 0
    nB = 0

    for _ in range(n):
        p, a = map(int, input().split())
        A[p] = a
        nA += a

    for _ in range(m):
        p, b = map(int, input().split())
        B[p] = b
        nB += b

    max_n = max(nA, nB)

    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i - 1] * i % MOD

    ifact = [1] * (max_n + 1)
    ifact[max_n] = pow(fact[max_n], MOD - 2, MOD)
    for i in range(max_n, 0, -1):
        ifact[i - 1] = ifact[i] * i % MOD

    # 片方にしか現れない素数 p では F_p は
    # 1/alpha_p! または 1/beta_p! という定数。
    # それらをまとめて scale とする。
    scale = 1

    # (多項式の長さ, tie-break用番号, F, H)
    heap = []
    serial = 0

    for p, a in A.items():
        b = B.get(p)

        if b is None:
            scale = scale * ifact[a] % MOD
            continue

        r = min(a, b)

        f = [0] * (r + 1)
        h = [0] * (r + 1)

        p_mod = p % MOD
        p_power = 1

        for i in range(r + 1):
            # [x^i] F_p
            f[i] = (
                p_power
                * ifact[i] % MOD
                * ifact[a - i] % MOD
                * ifact[b - i] % MOD
            )

            if i < r:
                # [x^(i+1)] H_p
                h[i + 1] = (
                    p_power
                    * ifact[i] % MOD
                    * ifact[a - i - 1] % MOD
                    * ifact[b - i - 1] % MOD
                )

            p_power = p_power * p_mod % MOD

        heappush(heap, (r + 1, serial, f, h))
        serial += 1

    for p, b in B.items():
        if p not in A:
            scale = scale * ifact[b] % MOD

    # 共通素因数がなければ、全ての組で LCA は根。
    if not heap:
        ans = scale * fact[nA] % MOD * fact[nB] % MOD
        print(ans)
        return

    # 小さい多項式から順にマージする。
    while len(heap) > 1:
        _, _, f1, h1 = heappop(heap)
        _, _, f2, h2 = heappop(heap)

        f, h = merge_pair(f1, h1, f2, h2)

        heappush(heap, (len(f), serial, f, h))
        serial += 1

    _, _, f, h = heap[0]

    ans = 0

    for i in range(len(f)):
        term = f[i] * fact[nA - i] % MOD
        term = term * fact[nB - i] % MOD
        term = term * fact[i] % MOD
        ans += term

    for i in range(1, len(h)):
        term = h[i] * fact[nA - i] % MOD
        term = term * fact[nB - i] % MOD
        term = term * fact[i - 1] % MOD
        ans -= term

    ans %= MOD
    ans = ans * scale % MOD

    print(ans)


if __name__ == "__main__":
    solve()