結果

問題 No.3589 Make Ends Meet (Hard)
コンテスト
ユーザー marc2825
提出日時 2026-07-10 10:03:59
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 134 ms / 2,000 ms
コード長 3,601 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 226 ms
コンパイル使用メモリ 95,980 KB
実行使用メモリ 87,168 KB
最終ジャッジ日時 2026-07-10 21:03:07
合計ジャッジ時間 5,498 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

MOD = 998244353


def solve() -> None:
    N, M, K = map(int, sys.stdin.readline().split())

    total_edges = N * (N - 1) // 2
    remaining_edges = total_edges - M

    limit = max(N, total_edges)

    fact = [1] * (limit + 1)
    for i in range(1, limit + 1):
        fact[i] = fact[i - 1] * i % MOD

    inv_fact = [1] * (limit + 1)
    inv_fact[limit] = pow(fact[limit], MOD - 2, MOD)

    for i in range(limit, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % MOD

    def comb(n: int, r: int) -> int:
        if r < 0 or r > n:
            return 0
        return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD

    small_comb = [[0] * (N + 1) for _ in range(N + 1)]
    for n in range(N + 1):
        for r in range(n + 1):
            small_comb[n][r] = comb(n, r)

    choose_remaining_edges = [
        comb(q, remaining_edges)
        for q in range(total_edges + 1)
    ]

    # dp[(used, last)][q]:
    # used 頂点を使い、最後の距離層のサイズが last である構成の
    # (1+x)^q 基底における係数
    dp: dict[tuple[int, int], list[int]] = {
        (1, 1): [1]
    }

    # L_1, ..., L_{K-1} を構成
    for layer in range(1, K):
        next_dp: dict[tuple[int, int], list[int]] = {}

        future_layers = K - 1 - layer

        for (used, previous_size), polynomial in dp.items():
            # 頂点 N は最後の集合 R に残す
            selectable = N - 1 - used

            # 残りの非空層に最低1頂点ずつ残す
            max_new_size = selectable - future_layers

            for new_size in range(1, max_new_size + 1):
                new_used = used + new_size
                key = (new_used, new_size)

                destination = next_dp.get(key)

                if destination is None:
                    max_degree = new_used * (new_used - 1) // 2
                    destination = [0] * (max_degree + 1)
                    next_dp[key] = destination

                choose_vertices = small_comb[selectable][new_size]
                internal_edges = new_size * (new_size - 1) // 2

                for j in range(new_size + 1):
                    coefficient = (
                        choose_vertices
                        * small_comb[new_size][j]
                        % MOD
                    )

                    if (new_size - j) & 1:
                        coefficient = MOD - coefficient

                    shift = internal_edges + previous_size * j

                    for q, value in enumerate(polynomial):
                        if value == 0:
                            continue

                        index = q + shift
                        destination[index] = (
                            destination[index]
                            + coefficient * value
                        ) % MOD

        dp = next_dp

    answer = 0

    for (used, last_size), polynomial in dp.items():
        rest_size = N - used

        # R内部、および R\{N} と最後の層の間の自由な辺
        free_edges = (
            rest_size * (rest_size - 1) // 2
            + last_size * (rest_size - 1)
        )

        for q, value in enumerate(polynomial):
            if value == 0:
                continue

            # 頂点Nと最後の層の間には1本以上の辺が必要
            ways = (
                choose_remaining_edges[q + free_edges + last_size]
                - choose_remaining_edges[q + free_edges]
            ) % MOD

            answer = (answer + value * ways) % MOD

    print(answer)


if __name__ == "__main__":
    solve()
0