AtCoder Regular Contest 176 （Sponsored by Mynavi）A,B,D,E問題メモ

from collections import Counter

n, m = map(int, input().split())
cols_cnt = Counter()
points = []
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    cols_cnt[b] += 1
    points.append((a, b))

rows = []
cols = [-1] * n
cc = 0
for c, v in cols_cnt.items():
    cc += v
    cols[cc - 1] = c
    for a, b in points:
        if b == c and a not in rows:
            rows.append(a)

rows_set = set(rows)
rows.extend(i for i in range(n) if i not in rows_set)
empty_cols = [j for j in range(n) if j not in cols_cnt]
jj = 0
for j in range(n):
    if cols[j] == -1:
        cols[j] = empty_cols[jj]
        jj += 1

print(n * m)
for ii in range(n):
    i = rows[ii]
    for jj in range(ii, ii + m):
        jj %= n
        j = cols[jj]
        print(i + 1, j + 1)

t = int(input())
for _ in range(t):
    n, m, k = map(int, input().split())

    if n < m:
        ans = [6, 2, 4, 8][n % 4]
        print(ans)
    elif m - 1 == k:
        ans = 0
        print(ans)
    else:
        p = m - k
        d = n % p

        d += (m // p) * p
        while d >= m:
            d -= p

        d %= 4
        ans = [6, 2, 4, 8][d]
        print(ans)

説明中では、3パターンにまでまとめられると言っているが、 この実装では、②と⑤、④と⑥がそれぞれ同じになることのみ利用して、5×5の遷移行列を計算している。

import numpy as np


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 get_matrix(n, MOD):
    facts, finvs = precompute_factorials(n, MOD)

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

    # 1回の入れ替えにより、隣り合った2つの状態の個数の変化を表す遷移行列。
    # 2つの初期状態が (X,Y)、入れ替わった後の状態を (x,y) とし、X,Yのいずれでもない数を Z とすると
    #   0: x=X, y=Y 初期から変わらない
    #   1: (x=X,y=Z) or (x=Z,y=Y) 一方のみ変わらず、もう一方が異なる数字が入っている
    #   2: x=Y, y=X 初期から入れ替わっている
    #   3: (x=Y,y=Z) or (x=Z,y=X) 一方にもう一方の数字が入り、もう一方は異なる数字が入っている
    #   4: x=Z, y=Z どちらにも、初期と異なる数字が入っている

    # ※後からわかったが、この場合分けは、より少ない (0,2),(1,3),(4) の3要素にまとめることができる

    mat = np.zeros((5, 5), np.int64)
    mat[0, 0] = ncr(n - 2, 2)
    mat[0, 1] = (n - 2) * 2
    mat[0, 2] = 1
    mat[1, 0] = 1
    mat[1, 1] = ncr(n - 1, 2) - 1
    mat[1, 3] = 2
    mat[1, 4] = n - 3
    mat[2, 0] = 1
    mat[2, 2] = ncr(n - 2, 2)
    mat[2, 3] = (n - 2) * 2
    mat[3, 1] = 2
    mat[3, 2] = 1
    mat[3, 3] = ncr(n - 1, 2) - 1
    mat[3, 4] = n - 3
    mat[4, 1] = 2
    mat[4, 3] = 2
    mat[4, 4] = ncr(n, 2) - 4 if n >= 4 else 0
    return mat

n, m = map(int, input().split())
ppp = list(map(int, input().split()))
MOD = 998244353

if n == 2:
    print(abs(ppp[0] - ppp[1]))
    exit()

mat = get_matrix(n, MOD)
base = np.eye(5, dtype=np.int64)
k = m
while k:
    if k & 1:
        base = base @ mat % MOD
    mat = mat @ mat % MOD
    k >>= 1

result = base[0]
INV2 = pow(2, -1, MOD)
INV_N2 = pow(n - 2, -1, MOD)
c1 = int(result[0] + result[2])  # 初期で隣り合った2つが（入れ替わっているかもしれないにせよ）隣り合った状況が変わらないパターン
c2 = int(result[1] + result[3]) * INV2 % MOD * INV_N2 % MOD  # 一方だけが残っているパターン（※1）
if n > 3:
    c3 = int(result[4] * 2) * INV_N2 % MOD * pow(n - 3, -1, MOD) % MOD  # 両方、いずれとも異なる数字になっているパターン（※2）
else:
    c3 = 0
# ※1: 続く差分の計算時、p1,p2 以外の N-2 個との差分の合計をまとめてかけるため、あらかじめ実際の個数の N-2 分の1倍しておく
# ※2: 続く差分の計算時、p1,p2 以外の数字のペア (N-2)(N-3)/2 個の差分の合計をまとめてかけるため、実際の個数の それ 分の1倍しておく

total_diff = []  # i を一方として、他のN-1個の数字との差分の絶対値の合計
for i in range(n):
    tmp = i * (i + 1) // 2 % MOD
    j = n - i - 1
    tmp += j * (j + 1) // 2
    total_diff.append(tmp % MOD)
all_total_diff = sum(total_diff) % MOD * INV2 % MOD

ans = 0
for i in range(n - 1):
    p1 = ppp[i] - 1
    p2 = ppp[i + 1] - 1
    d = abs(p1 - p2)
    others = all_total_diff - total_diff[p1] - total_diff[p2] + d
    ans += d * c1 % MOD
    ans += (total_diff[p1] - d + total_diff[p2] - d) * c2 % MOD
    ans += others * c3 % MOD
    ans %= MOD

print(ans)

from collections import deque
from typing import Tuple, List


class Dinic:
    """
    Usage:
       mf = Dinic(n)
    -> mf.add_link(from, to, capacity)
    -> mf.max_flow(source, target)
    """

    def __init__(self, n: int):
        self.n = n
        self.links: List[List[List[int]]] = [[] for _ in range(n)]
        # if exists an edge (v→u, capacity)...
        #   links[v] = [ [ capacity, u, index of rev-edge in links[u], is_original_edge ], ]

    def add_link(self, from_: int, to: int, capacity: int) -> None:
        self.links[from_].append([capacity, to, len(self.links[to]), 1])
        self.links[to].append([0, from_, len(self.links[from_]) - 1, 0])

    def bfs(self, s: int) -> List[int]:
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev, _ in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        return depth

    def dfs(self, s: int, t: int, depth: List[int], progress: List[int], link_counts: List[int]) -> int:
        links = self.links
        stack = [s]

        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                cap, to, rev, _ = links[v][i]
                if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
                    continue
                stack.append(to)
                break
            else:
                progress[v] += 1
                stack.pop()
        else:
            return 0

        f = 1 << 60
        fwd_links = []
        bwd_links = []
        for v in stack[:-1]:
            cap, to, rev, _ = link = links[v][progress[v]]
            f = min(f, cap)
            fwd_links.append(link)
            bwd_links.append(links[to][rev])

        for link in fwd_links:
            link[0] -= f

        for link in bwd_links:
            link[0] += f

        return f

    def max_flow(self, s: int, t: int) -> int:
        link_counts = list(map(len, self.links))
        flow = 0
        while True:
            depth = self.bfs(s)
            if depth[t] < 0:
                break
            progress = [0] * self.n
            current_flow = self.dfs(s, t, depth, progress, link_counts)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, depth, progress, link_counts)
        return flow

    def cut_edges(self, s: int) -> List[Tuple[int, int]]:
        """ max_flowしたあと、最小カットにおいてカットすべき辺を復元する """
        q = [s]
        reachable = [0] * self.n
        reachable[s] = 1
        while q:
            v = q.pop()
            for cap, u, li, _ in self.links[v]:
                if cap == 0 or reachable[u]:
                    continue
                reachable[u] = 1
                q.append(u)
        edges = []
        for v in range(self.n):
            if reachable[v] == 0:
                continue
            for cap, u, li, orig in self.links[v]:
                if orig == 1 and reachable[u] == 0:
                    edges.append((v, u))
        return edges


n, m = map(int, input().split())
xxx = list(map(int, input().split()))
yyy = list(map(int, input().split()))
aaaaaa = [list(map(int, input().split())) for _ in range(m)]

max_a = max(max(map(max, aaaaaa)), max(xxx), max(yyy))
dnc = Dinic(n * max_a * 2 + m + 2)

s = n * max_a * 2 + m
t = s + 1
INF = 1 << 60

offset1 = n * max_a
offset2 = n * max_a * 2

for k in range(n):
    x = xxx[k]
    u = k * max_a + x - 1
    dnc.add_link(s, u, INF)
    for j in range(x, max_a):
        u1 = k * max_a + j - 1
        u2 = u1 + 1
        dnc.add_link(u1, u2, j)
        dnc.add_link(u2, u1, INF)
    u1 = k * max_a + max_a - 1
    dnc.add_link(u1, t, max_a)

    y = yyy[k]
    v = offset1 + k * max_a + y - 1
    dnc.add_link(v, t, INF)
    for j in range(y, max_a):
        v1 = offset1 + k * max_a + j - 1
        v2 = v1 + 1
        dnc.add_link(v2, v1, j)
        dnc.add_link(v1, v2, INF)
    v1 = offset1 + k * max_a + max_a - 1
    dnc.add_link(s, v1, max_a)

for i in range(m):
    u = offset2 + i
    aaa = aaaaaa[i]
    for k in range(n):
        a = aaa[k]
        v = k * max_a + a - 1
        dnc.add_link(u, v, INF)
        v = offset1 + k * max_a + a - 1
        dnc.add_link(v, u, INF)

ans = dnc.max_flow(s, t)
print(ans)