オムロンプログラミングコンテスト2025 #2（AtCoder Beginner Contest 432）D,E,F,G問題メモ

from atcoder.dsu import DSU


def solve(n, x, y, storms):
    q = [(0, 0, x, y)]
    for c, a, b in storms:
        a = int(a)
        b = int(b)
        nq = []
        for lx, ly, rx, ry in q:
            if c == 'X':
                if rx <= a:
                    nq.append((lx, ly - b, rx, ry - b))
                elif lx < a < rx:
                    nq.append((lx, ly - b, a, ry - b))
                    nq.append((a, ly + b, rx, ry + b))
                else:
                    nq.append((lx, ly + b, rx, ry + b))
            else:
                if ry <= a:
                    nq.append((lx - b, ly, rx - b, ry))
                elif ly < a < ry:
                    nq.append((lx - b, ly, rx - b, a))
                    nq.append((lx + b, a, rx + b, ry))
                else:
                    nq.append((lx + b, ly, rx + b, ry))
        q = nq
    m = len(q)
    uft = DSU(m)
    for i in range(m):
        lx1, ly1, rx1, ry1 = q[i]
        for j in range(i + 1, m):
            lx2, ly2, rx2, ry2 = q[j]
            if rx1 == lx2 or rx2 == lx1:
                if ry1 > ly2 and ry2 > ly1:
                    uft.merge(i, j)
            if ry1 == ly2 or ry2 == ly1:
                if rx1 > lx2 and rx2 > lx1:
                    uft.merge(i, j)
    sizes = [0] * m
    for i in range(m):
        lx, ly, rx, ry = q[i]
        leader = uft.leader(i)
        sizes[leader] += (rx - lx) * (ry - ly)
    ans = [s for s in sizes if s != 0]
    ans.sort()
    return ans


n, x, y = list(map(int, input().split()))
storms = [input().split() for _ in range(n)]
ans = solve(n, x, y, storms)
print(len(ans))
print(*ans)

from atcoder.fenwicktree import FenwickTree


def solve(n, q, aaa, queries):
    count = FenwickTree(500_001)
    total = FenwickTree(500_001)
    for a in aaa:
        count.add(a, 1)
        total.add(a, a)
    buf = []
    for op, x, y in queries:
        if op == 1:
            x -= 1
            prev = aaa[x]
            aaa[x] = y
            count.add(prev, -1)
            total.add(prev, -prev)
            count.add(y, 1)
            total.add(y, y)
        else:
            l = x
            r = y
            if l >= r:
                buf.append(l * n)
                continue
            lc = count.sum(0, l)
            rc = n - count.sum(0, r)
            buf.append(l * lc + r * rc + total.sum(l, r))
    return buf


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

def solve(n, aaa):
    def iter_bit(bitset):
        while bitset:
            lsb = bitset & -bitset
            yield lsb
            bitset ^= lsb

    d, m = divmod(sum(aaa), n)
    if m != 0:
        return None
    mapping = [-1] * n
    bbb = []
    for i, a in enumerate(aaa, start=1):
        a -= d
        if a == 0:
            continue
        mapping[len(bbb)] = i
        bbb.append(a)
    aaa = bbb
    n = len(aaa)
    if n == 0:
        return []

    n2 = 1 << n
    pt = [0] * n2
    back = [-1] * n2
    dp = [0] * n2
    for bitset in range(1, n2):
        lsb = bitset & -bitset
        pt[bitset] = pt[bitset ^ lsb] + aaa[lsb.bit_length() - 1]
        for b in iter_bit(bitset):
            new = dp[bitset ^ b] + int(pt[bitset ^ b] == 0)
            if dp[bitset] < new:
                dp[bitset] = new
                back[bitset] = bitset ^ b
    remain = n2 - 1

    groups = []
    while remain:
        tmp = 0
        while dp[remain] == dp[back[remain]]:
            tmp |= remain ^ back[remain]
            remain = back[remain]
        tmp |= remain ^ back[remain]
        remain = back[remain]
        groups.append(tmp)

    ans = []
    for grp in groups:
        minus = []
        plus = []
        for bit in iter_bit(grp):
            i = bit.bit_length() - 1
            if aaa[i] < 0:
                minus.append((mapping[i], -aaa[i]))
            else:
                plus.append((mapping[i], aaa[i]))
        while len(minus) > 0 and len(plus) > 0:
            i, a = minus.pop()
            j, b = plus.pop()
            if a == b:
                ans.append(f'{j} {i} {a}')
            elif a > b:
                ans.append(f'{j} {i} {b}')
                minus.append((i, a - b))
            else:
                ans.append(f'{j} {i} {a}')
                plus.append((j, b - a))
    return ans


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
if ans is None:
    print(-1)
else:
    print(len(ans))
    print('\n'.join(ans))

import numpy as np
import numpy.typing as npt
import numba


@numba.njit('(i8[:],i8[:])', cache=True)
def convolve_998244353(aaa: npt.NDArray[np.int64], bbb: npt.NDArray[np.int64]) -> npt.NDArray[np.int64]:
    MOD = 998244353
    SUM_E = np.array(
        [911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456,
         131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443,
         56250497, 867605899, 0, 0, 0, 0, 0, 0, 0, 0], np.int64)
    SUM_IE = np.array(
        [86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882,
         927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183,
         824071951, 103369235, 0, 0, 0, 0, 0, 0, 0, 0], np.int64)

    def bit_length(n):
        x = 0
        while 1 << x < n:
            x += 1
        return x

    def bit_scan_forward(n):
        x = 0
        while n & 1 == 0:
            n >>= 1
            x += 1
        return x

    def mod_pow(x, a, MOD):
        ret = 1
        cur = x
        while a > 0:
            if a & 1:
                ret = ret * cur % MOD
            cur = cur * cur % MOD
            a >>= 1
        return ret

    def butterfly(aaa, mod, sum_e):
        n = aaa.size
        h = bit_length(n)

        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p] * now % mod
                    aaa[i + offset] = (l + r) % mod
                    aaa[i + offset + p] = (l - r) % mod
                now = now * sum_e[bit_scan_forward(~s)] % mod

    def butterfly_inv(aaa, mod, sum_ie):
        n = aaa.size
        h = bit_length(n)

        for ph in range(h, 0, -1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p]
                    aaa[i + offset] = (l + r) % mod
                    aaa[i + offset + p] = ((l - r) * inow) % mod
                inow = inow * sum_ie[bit_scan_forward(~s)] % mod

    n = aaa.size
    m = bbb.size
    k = n + m - 1
    z = 1 << bit_length(k)
    raaa = np.zeros(z, np.int64)
    rbbb = np.zeros(z, np.int64)
    raaa[:n] = aaa
    rbbb[:m] = bbb
    butterfly(raaa, MOD, SUM_E)
    butterfly(rbbb, MOD, SUM_E)
    for i in range(z):
        raaa[i] = raaa[i] * rbbb[i] % MOD
    butterfly_inv(raaa, MOD, SUM_IE)
    iz = mod_pow(z, MOD - 2, MOD)
    for i in range(k):
        raaa[i] = raaa[i] * iz % MOD
    return raaa[:k]


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, m, aaa, bbb):
    MAX_V = 500_000
    MOD = 998244353
    facts, finvs = precompute_factorials(MAX_V, MOD)
    fff = [0] * (MAX_V + 1)
    ggg = [0] * (MAX_V + 1)
    for a in aaa:
        fff[a] += facts[a]
    for b in bbb:
        ggg[-b] += finvs[b]
    fff = np.array(fff, np.int64)
    ggg = np.array(ggg, np.int64)
    hhh = convolve_998244353(fff, ggg)[MAX_V + 1:].tolist()
    ans = 0
    for i in range(MAX_V):
        if hhh[i] != 0:
            ans += hhh[i] * finvs[i]
            ans %= MOD
    return ans


n, m = list(map(int, input().split()))
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ans = solve(n, m, aaa, bbb)
print(ans)