#1167738 (PyPy3) No.3589 Make Ends Meet (Hard)

• 問題: No.3589 Make Ends Meet (Hard)
• ユーザー: marc2825
• 提出日時: 2026-05-30 09:41:46
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 1,234 ms / 2,000 ms
• コード長: 4,055 bytes
• コンパイル時間: 237 ms
• コンパイル使用メモリ: 96,108 KB
• 実行使用メモリ: 117,760 KB
• 最終ジャッジ日時: 2026-07-10 20:58:56
• 合計ジャッジ時間: 8,570 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 47

ソースコード

import sys

MOD = 998244353

def main():
    N, M, K = map(int, sys.stdin.readline().split())

    E = N * (N - 1) // 2
    R = E - M

    if R < 0:
        print(0)
        return

    # comb[n][r] for n <= E
    comb = [[0] * (R + 1) for _ in range(E + 1)]
    for i in range(E + 1):
        comb[i][0] = 1
        for j in range(1, min(i, R) + 1):
            if j == i:
                comb[i][j] = 1
            else:
                comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD

    # vertex combinations
    C = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        C[i][0] = C[i][i] = 1
        for j in range(1, i):
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD

    def multiply(poly, terms):
        res = [0] * (R + 1)
        for i, a in enumerate(poly):
            if a == 0:
                continue
            for d, b in terms:
                if i + d > R:
                    break
                res[i + d] = (res[i + d] + a * b) % MOD
        return res

    def one_plus_x_pow(t):
        return [(i, comb[t][i]) for i in range(min(t, R) + 1) if comb[t][i]]

    # trans[p][q]:
    # 前層サイズ p、現在層サイズ q のとき、
    # 現在層内部の辺は自由、
    # 現在層の各頂点は前層へ少なくとも1本辺を持つ
    trans = [[None] * (N + 1) for _ in range(N + 1)]

    for p in range(1, N + 1):
        for q in range(1, N + 1):
            if p + q > N:
                continue

            inside = q * (q - 1) // 2
            arr = [0] * (R + 1)

            # (1+x)^inside * ((1+x)^p - 1)^q
            # = sum_r (-1)^(q-r) C(q,r) (1+x)^(inside + p*r)
            for r in range(q + 1):
                sign = 1 if (q - r) % 2 == 0 else -1
                coef = C[q][r]
                total = inside + p * r

                for d in range(min(total, R) + 1):
                    val = comb[total][d] * coef % MOD
                    if sign == 1:
                        arr[d] = (arr[d] + val) % MOD
                    else:
                        arr[d] = (arr[d] - val) % MOD

            trans[p][q] = [(i, v) for i, v in enumerate(arr) if v]

    mid = N - 2

    # dp[(used, last_size)] = polynomial
    # used: 中間頂点 2..N-1 のうち、すでに距離層に使った数
    # last_size: 直前の距離層サイズ
    dp = {(0, 1): [1] + [0] * R}  # L0 = {1}

    # L1, ..., L_{K-1}
    for _ in range(1, K):
        ndp = {}

        for (used, prev_size), poly in dp.items():
            remain = mid - used

            for cur_size in range(1, remain + 1):
                if trans[prev_size][cur_size] is None:
                    continue

                ways = C[remain][cur_size]
                npoly = multiply(poly, trans[prev_size][cur_size])

                if ways != 1:
                    npoly = [x * ways % MOD for x in npoly]

                key = (used + cur_size, cur_size)
                if key not in ndp:
                    ndp[key] = npoly
                else:
                    old = ndp[key]
                    for i in range(R + 1):
                        old[i] = (old[i] + npoly[i]) % MOD

        dp = ndp

    ans = 0

    # LK には頂点 N が必ず入る
    for (used, prev_size), poly in dp.items():
        remain = mid - used

        for t in range(remain + 1):
            # LK のサイズ = N + 中間頂点 t 個
            cur_size = t + 1

            if trans[prev_size][cur_size] is None:
                continue

            ways = C[remain][t]

            poly2 = multiply(poly, trans[prev_size][cur_size])

            if ways != 1:
                poly2 = [x * ways % MOD for x in poly2]

            # B: 距離 K より大きい、または到達不能な頂点
            b = remain - t

            # B内部の辺と、B-LK間の辺は自由
            free = b * (b - 1) // 2 + b * cur_size

            poly3 = multiply(poly2, one_plus_x_pow(free))

            ans = (ans + poly3[R]) % MOD

    print(ans)


if __name__ == "__main__":
    main()