デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）D,F,G,Ex問題メモ

a, b, c, d = map(int, input().split())
l = d - c + 1

prime = [0, 1] * 101
prime[1] = 0
prime[2] = 1
for i in range(3, 15, 2):
    if prime[i]:
        for j in range(i * i, 201, i):
            prime[j] = 0

s = sum(prime[:l])
win = [0] * 201
for i in range(201 - l):
    if s == 0:
        win[i] = 1
    s += prime[i + l]
    s -= prime[i]

if sum(win[a + c:b + c + 1]) == 0:
    print('Aoki')
else:
    print('Takahashi')

from collections import defaultdict
from heapq import heapify, heappop, heappush


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return False
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
        return True

    def get_size(self, x):
        return -self.table[self.root(x)]


n, m = map(int, input().split())
ddd = list(map(int, input().split()))

if sum(ddd) != 2 * (n - 1):
    print(-1)
    exit()

uft = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ddd[a] -= 1
    ddd[b] -= 1
    if ddd[a] < 0 or ddd[b] < 0 or not uft.unite(a, b):
        print(-1)
        exit()

extra_i = defaultdict(list)
extra_c = defaultdict(int)
for i in range(n):
    if ddd[i] > 0:
        r = uft.root(i)
        extra_i[r].append(i)
        extra_c[r] += ddd[i]

q = []
for r, c in extra_c.items():
    q.append((-c, r))

heapify(q)
ans = []

for _ in range(n - m - 1):
    if len(q) < 2:
        print(-1)
        exit()
    c1, r1 = heappop(q)
    c2, r2 = heappop(q)
    u = extra_i[r1][-1]
    v = extra_i[r2][-1]
    ddd[u] -= 1
    ddd[v] -= 1
    ans.append(f'{u + 1} {v + 1}')

    if ddd[u] == 0:
        extra_i[r1].pop()
    if ddd[v] == 0:
        extra_i[r2].pop()

    extra_i[r1].extend(extra_i[r2])
    heappush(q, (c1 + c2 + 2, r1))

print('\n'.join(ans))

from collections import deque
from typing import List, Tuple


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 mf.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 mf.links[v]:
                if orig == 1 and reachable[u] == 0:
                    edges.append((v, u))
        return edges


n, m = map(int, input().split())
mf = Dinic(n * 2)
INF = 1 << 60
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    mf.add_link(a + n, b, INF)
    if a != 0 and b != n - 1:
        mf.add_link(b + n, a, INF)
ccc = list(map(int, input().split()))
for i, c in enumerate(ccc):
    if c > 0:
        mf.add_link(i, i + n, c)
    else:
        mf.add_link(i, i + n, INF)

ans = mf.max_flow(0, n - 1)
print(ans)

edges = mf.cut_edges(0)
used = [f + 1 for f, t in edges if t == f + n]

print(len(used))
print(*used)

memo = {}


def solve(d):
    # d: あと何倍まではゴールできない（M//x）
    # return: その時の残り回数期待値

    # memo1: d < sqrt(m) の値を格納
    # memo2: d >= sqrt(m) の値は、それに該当する x が1通りに確定するので、その値で格納
    if d in memo:
        return memo[d]

    res = n
    l = 2  # 遷移先のdが同じになるダイスの目の、現在考慮中の下限
    while l <= n:
        new_d = d // l
        if new_d == 0:
            break
        r = min(n, d // new_d)  # 上限
        res += (r - l + 1) * solve(new_d)
        res %= MOD
        l = r + 1
    res *= inv_n1
    res %= MOD
    memo[d] = res
    return res


n, m = map(int, input().split())
MOD = 10 ** 9 + 7
inv_n1 = pow(n - 1, MOD - 2, MOD)

ans = solve(m)
print(ans)