AtCoder Beginner Contest 419 E,F,G 問題メモ

from collections import Counter


def solve(n, m, l, aaa):
    groups = [[] for _ in range(l)]
    for i, a in enumerate(aaa):
        groups[i % l].append(a)
    INF = 1 << 60
    dp = [INF] * m
    dp[0] = 0
    for grp in groups:
        total = sum(grp)
        size = len(grp)
        cnt = Counter(grp)
        items = []
        large = 0
        for a, c in sorted(cnt.items(), reverse=True):
            items.append((a, a * size + m * large - total))
            large += c
        ndp = [INF] * m
        for i in range(m):
            for s, c in items:
                key = (i + s) % m
                ndp[key] = min(ndp[key], dp[i] + c)
        dp = ndp

    ans = dp[0]
    min_group = n // l
    for i in range(1, m):
        ans = min(ans, dp[i] + (m - i) * min_group)
    return ans


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

from collections import deque


class AhoCorasick:

    def __init__(self, patterns):
        self.patterns = patterns
        self.children = [{}]
        self.match = [[]]

        for pi, pattern in enumerate(patterns):
            self._register(pi, pattern)

        self.failure = [0] * len(self.children)
        self._create_failure()

    def _register(self, pi, pattern):
        k = 0
        for c in pattern:
            if c in self.children[k]:
                k = self.children[k][c]
            else:
                j = len(self.children)
                self.children[k][c] = j
                self.children.append({})
                self.match.append([])
                k = j
        self.match[k].append(pi)

    def _create_failure(self):
        children = self.children
        match = self.match
        failure = self.failure

        q = deque(children[0].values())
        while q:
            k = q.popleft()
            b = failure[k]
            for c, j in children[k].items():
                failure[j] = self._next(b, c)
                match[j].extend(match[failure[j]])
                q.append(j)

    def _next(self, k, c):
        while True:
            if c in self.children[k]:
                return self.children[k][c]
            if k == 0:
                return 0
            k = self.failure[k]

    def search(self, target):
        match = self.match
        patterns = self.patterns

        k = 0
        matched = []
        for i, c in enumerate(target):
            k = self._next(k, c)
            matched.extend((i - len(patterns[m]) + 1, i, patterns[m]) for m in match[k])
        return matched


def solve(n, l, sss):
    act = AhoCorasick(sss)
    m = len(act.children)
    accept_flags = [0] * m
    for i in range(m):
        for j in act.match[i]:
            accept_flags[i] |= 1 << j

    children = [[0] * 26 for _ in range(m)]
    for i in range(m):
        for c in range(26):
            children[i][c] = act._next(i, chr(c + 97))

    n2 = 1 << n
    dp = [[0] * n2 for _ in range(m)]
    dp[0][0] = 1
    MOD = 998244353
    for _ in range(l):
        ndp = [[0] * n2 for _ in range(m)]
        for i in range(m):
            for bitset in range(n2):
                pat = dp[i][bitset]
                if pat == 0:
                    continue
                for c in range(26):
                    j = children[i][c]
                    ndp[j][bitset | accept_flags[j]] += dp[i][bitset]
        dp = ndp
        for i in range(m):
            for bitset in range(n2):
                dp[i][bitset] %= MOD

    ans = sum(dp[i][-1] for i in range(m))
    ans %= MOD
    return ans


n, l = map(int, input().split())
sss = [input() for _ in range(n)]
ans = solve(n, l, sss)
print(ans)

from typing import Sequence


def trim_dead_end(n: int, links: list[list[int]], special: Sequence[int] = None):
    """ 次数1の頂点を（連鎖的に）除去
    Args:
        n: 頂点数
        links: 隣接リスト
        special: 次数1であっても除去しない頂点群

    Returns:
        links: 新しい隣接リスト
        mapping: 旧頂点番号→新頂点番号への変換辞書
    """
    if special is None:
        special = set()
    else:
        special = set(special)
    links = list(map(set, links))
    q = [u for u in range(n) if len(links[u]) == 1 and u not in special]
    available = set(range(n))
    while q:
        u = q.pop()
        if len(links[u]) == 0:
            continue
        available.remove(u)
        v = next(iter(links[u]))
        links[v].remove(u)
        if len(links[v]) == 1 and v not in special:
            q.append(v)
    available = sorted(available)
    mapping = {a: i for i, a in enumerate(available)}
    links = [[mapping[v] for v in links[u]] for u in available]
    return links, mapping


def contract(n: int, links: list[list[int]], special: Sequence[int] = None):
    """ 次数2のパスを縮約

    Args:
        n: 頂点数
        links: 隣接リスト
        special: 次数2であっても縮約しない頂点群

    Returns:
        result[u] = [(v, c), (v, c), ...]: 縮約し、縮約前の距離の情報を加えた隣接リスト
        mapping: 旧頂点番号→新頂点番号への変換辞書
    """

    def follow(u, v):
        """ u から v 方向に、次のメイン頂点まで探索する """
        cost = 1
        while v not in mapping:
            assert len(links[v]) == 2
            if links[v][0] == u:
                u, v = v, links[v][1]
            else:
                u, v = v, links[v][0]
            cost += 1
        return u, v, cost

    main_vertices = {u for u in range(n) if len(links[u]) != 2}
    if special is not None:
        main_vertices.update(special)
    main_vertices = sorted(main_vertices)
    m = len(main_vertices)
    mapping = {u: i for i, u in enumerate(main_vertices)}
    result = [[] for _ in range(m)]
    contracted = [set() for _ in range(m)]
    for u in main_vertices:
        uu = mapping[u]
        for v in links[u]:
            if v in contracted[uu]:
                continue
            p, v, cost = follow(u, v)
            vv = mapping[v]
            result[uu].append((vv, cost))
            result[vv].append((uu, cost))
            contracted[vv].add(p)
    return result, mapping


def dfs(links, s, g, original_n):
    result = [0] * original_n

    n = len(links)
    used = [False] * n
    stack = [(s, 0, iter(links[s]))]
    used[s] = True

    while stack:
        u, l, it = stack[-1]
        try:
            v, c = next(it)
        except StopIteration:
            # u の探索終了
            stack.pop()
            used[u] = False
            continue

        if used[v]:
            continue
        if v == g:
            result[l + c] += 1
        else:
            used[v] = True
            stack.append((v, l + c, iter(links[v])))

    return result


def solve(n, m, edges):
    links = [[] for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].append(v)
        links[v].append(u)
    trimmed_links, mapping = trim_dead_end(n, links, (0, n - 1))
    nn = len(trimmed_links)
    s = mapping[0]
    g = mapping[n - 1]
    contracted_links, mapping = contract(nn, trimmed_links, (s, g))
    s = mapping[s]
    g = mapping[g]
    used = [False] * len(contracted_links)
    used[s] = True
    ans = dfs(contracted_links, s, g, n)
    return ans[1:]


n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, edges)
print(*ans)