AtCoder Regular Contest 197 (Div. 2) A,B,C,D,E問題メモ

def solve(h, w, s):
    rc = s.count('R')
    dc = s.count('D')
    rem_rc = w - 1 - rc
    rem_dc = h - 1 - dc
    x1 = []
    x2 = []
    for i, c in enumerate(s):
        if c == '?':
            if rem_rc > 0:
                x1.append('R')
                rem_rc -= 1
            else:
                x1.append('D')
            if rem_dc > 0:
                x2.append('D')
                rem_dc -= 1
            else:
                x2.append('R')
        else:
            x1.append(c)
            x2.append(c)

    def make_path(x):
        first_col = [0]
        last_col = []
        j = 0
        for c in x:
            if c == 'D':
                first_col.append(j)
                last_col.append(j)
            else:
                j += 1
        last_col.append(w - 1)
        return first_col, last_col

    fc1, lc1 = make_path(x1)
    fc2, lc2 = make_path(x2)
    ans = 0
    for i in range(h):
        ans += lc1[i] - fc2[i] + 1
    return ans


t = int(input())
for _ in range(t):
    h, w = map(int, input().split())
    s = input()
    ans = solve(h, w, s)
    print(ans)

from bisect import bisect


def solve(n, aaa):
    aaa.sort()
    total = 0
    ans = 0
    for i, a in enumerate(aaa, start=1):
        total += a
        ave = total // i
        x = bisect(aaa, ave)
        ans = max(ans, i - x)
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    print(ans)

from operator import add
from typing import Callable, Any
import sys

input = sys.stdin.buffer.readline


class SegmentTreeInjectable:
    """
    単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木

    [生成]
    SegmentTreeInjectable(n, identity_factory, func)
    SegmentTreeInjectable.from_array(array, identity_factory, func)  # 既存の配列より作成

    [関数]
    add(i, x)               Aiにxを加算
    update(i, x)            Aiをxに書き換え
    get_range(a, b)         [a, b) の集約値を得る
    get_all()               全ての集約値を得る
    get_point(i)            Aiを得る
    leftmost(a, b, x, ev)   [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
    rightmost(a, b, x, ev)  [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
    debug_print()           深さ毎に整形して出力する
    """

    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.n = n
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory

    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins

    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)

    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)

    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            i >>= 1
            lch = i << 1
            rch = lch | 1
            tree[i] = func(tree[lch], tree[rch])

    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return func(result_l, result_r)

    def get_all(self):
        return self.tree[1]

    def get_point(self, i):
        return self.tree[i + self.offset]

    def max_right(self, l: int, f: Callable[[Any], bool]) -> int:
        """
        [l,r) の集約値を op(l,r) としたとき、以下を満たす l <= r <= N の値 r のいずれか1つを得る。
          * f(op(l, r)) = True または r=l
          * f(op(l, r+1)) = False または r=N

        fが単調性を満たす場合、集約値で右端を二分探索する関数と解釈できる。
        """
        assert 0 <= l <= self.n

        if l == self.n:
            return self.n

        l += self.offset
        sm = self.idf()
        func = self.func
        tree = self.tree

        first = True
        while first or (l & -l) != l:
            first = False
            while l & 1 == 0:
                l >>= 1
            if not f(func(sm, tree[l])):
                while l < self.offset:
                    l <<= 1
                    tmp = func(sm, tree[l])
                    if f(tmp):
                        sm = tmp
                        l += 1
                return l - self.offset
            sm = func(sm, tree[l])
            l += 1

        return self.n

    def leftmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。

        Notes:
            "単体で" ev を満たす要素位置を求める関数である点に注意。
            a,a+1,a+2,... の集約値で評価する場合は max_right の方を使う。

        使用できる条件:
            [l, r) の集約値を f(l,r) としたとき、以下の2つが同値である。（(func, ev) = (min,ge), (max,le) など）
            ev(x, f(l,r))=True である ⇔ l <= i < r 内に ev(x, Ai)=True となる要素がある

        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        r_found = -1
        while l < r:
            if l & 1:
                if ev(x, tree[l]):
                    return self._leftmost_sub(l, x, ev)
                l += 1
            if r & 1:
                if ev(x, tree[r - 1]):
                    r_found = r - 1
            l >>= 1
            r >>= 1

        if r_found == -1:
            return -1

        return self._leftmost_sub(r_found, x, ev)

    def _leftmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l]):
                i = l
            else:
                i = l + 1
        return i - self.offset

    def rightmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        l_found = -1
        while l < r:
            if r & 1:
                if ev(x, tree[r - 1]):
                    return self._rightmost_sub(r - 1, x, ev)
            if l & 1:
                if ev(x, tree[l]):
                    l_found = l
                l += 1
            l >>= 1
            r >>= 1

        if l_found == -1:
            return -1

        return self._rightmost_sub(l_found, x, ev)

    def _rightmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l + 1]):
                i = l + 1
            else:
                i = l
        return i - self.offset

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1


def solve(q, queries):
    limit = 1 << 22
    init = [1] * limit
    init[0] = 0
    fwt = SegmentTreeInjectable.from_array(init, int, add)

    def update(a):
        if a >= limit:
            return
        if fwt.get_point(a) == 0:
            return
        fwt.update(a, 0)
        for b in range(a + a, limit, a):
            if fwt.get_point(b) == 1:
                fwt.update(b, 0)

    buf = []
    for a, b in queries:
        update(a)
        ans = fwt.max_right(0, lambda x: x < b)
        buf.append(ans)
    return buf


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

from collections import defaultdict


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


def solve(n, aaa):
    full = (1 << n) - 1
    if aaa[0] != full:
        return 0

    loc = defaultdict(list)
    for i in range(n):
        loc[aaa[i]].append(i)

    keys = list(loc.keys())
    keys.sort(key=lambda bit: (bit ^ full).bit_count())

    groups = []
    for k in keys:
        g = 0
        for l in loc[k]:
            g |= 1 << l
        groups.append(g)

    m = len(loc)
    for i in range(1, m):
        ki = keys[i]
        for j in range(i):
            kj = keys[j]
            if ki & kj == ki:
                if ki & groups[j] != groups[j]:
                    return 0
            else:
                if kj & groups[i] != 0:
                    return 0
                if ki & groups[j] != 0:
                    return 0

    MOD = 998244353
    lens = list(map(len, loc.values()))
    mx = max(lens)
    facts = precompute_factorials(mx, MOD)
    ans = facts[lens[0] - 1]
    for l in lens[1:]:
        ans *= facts[l]
        ans %= MOD
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = []
    for _ in range(n):
        row = int(input().replace(' ', '')[::-1], base=2)
        aaa.append(row)
    ans = solve(n, aaa)
    print(ans)

def solve(n, h, w):
    if h < 2 * n or w < 2 * n:
        return 0

    MOD = 998244353
    h4 = (h - 2 * n + 1) * (h - 2 * n + 2) * (h - 2 * n + 3) * (h - 2 * n + 4) // 24 % MOD
    h3 = (h - 2 * n + 1) * (h - 2 * n + 2) * (h - 2 * n + 3) // 6 % MOD
    h2 = (h - 2 * n + 1) * (h - 2 * n + 2) // 2 % MOD
    pat_h = (h4 * 5 - h3 * 5 + h2) % MOD
    pat_w = ((w - 2 * n + 1) * (w - 2 * n + 2) // 2) ** 2 % MOD
    pat_dh = (h - 2 * n) * (h - 2 * n + 1) * (h - 2 * n + 2) * (h - 2 * n + 3) // 24 % MOD
    pat_dw = (w - 2 * n) * (w - 2 * n + 1) * (w - 2 * n + 2) * (w - 2 * n + 3) // 24 % MOD
    pat_sh = (h4 * 4 - h3 * 4 + h2) % MOD
    tmp = (pat_h * pat_w) - (pat_dh * pat_dw) % MOD
    tmp *= 2
    tmp -= pat_sh * pat_w
    tmp %= MOD
    return tmp


t = int(input())
for _ in range(t):
    n, h, w = map(int, input().split())
    ans = solve(n, h, w)
    print(ans)

def solve(n, h, w):
    if h < 2 * n or w < 2 * n:
        return 0

    MOD = 998244353
    h2 = (h - 2 * n + 1) * (h - 2 * n + 2) // 2 % MOD
    w2 = (w - 2 * n + 1) * (w - 2 * n + 2) // 2 % MOD
    pat_dh = (h - 2 * n) * (h - 2 * n + 1) * (h - 2 * n + 2) * (h - 2 * n + 3) // 24 % MOD
    pat_dw = (w - 2 * n) * (w - 2 * n + 1) * (w - 2 * n + 2) * (w - 2 * n + 3) // 24 % MOD
    ans = (h2 * w2) ** 2 - 2 * (pat_dh * pat_dw)
    ans %= MOD
    return ans


t = int(input())
for _ in range(t):
    n, h, w = map(int, input().split())
    ans = solve(n, h, w)
    print(ans)