結果

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

ソースコード

diff #
raw source code 

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]
    MAXE = E
    comb = [[0] * (MAXE + 1) for _ in range(MAXE + 1)]
    for i in range(MAXE + 1):
        comb[i][0] = comb[i][i] = 1
        for j in range(1, i):
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD

    # small combination for choosing vertices
    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 poly_pow_one_plus_x(t):
        """(1+x)^t truncated to degree R"""
        deg = min(t, R)
        return [(i, comb[t][i]) for i in range(deg + 1) if comb[t][i]]

    # trans[p][q]:
    # previous layer size = p, current layer size = q
    # current layer internal edges: (1+x)^C(q,2)
    # edges from previous layer to current layer:
    # each current vertex must have at least one edge to previous layer
    #
    # polynomial:
    # (1+x)^C(q,2) * ((1+x)^p - 1)^q
    trans = [[None] * (N + 1) for _ in range(N + 1)]

    for p in range(1, N + 1):
        for q in range(1, N + 1):
            base_inside = q * (q - 1) // 2
            arr = [0] * (R + 1)

            # inclusion-exclusion:
            # ((1+x)^p - 1)^q
            # = sum_{r=0}^{q} (-1)^{q-r} C(q,r) (1+x)^{pr}
            for r in range(q + 1):
                sign = 1 if (q - r) % 2 == 0 else -1
                coef = C[q][r]
                total_edges = base_inside + p * r

                upto = min(total_edges, R)
                for d in range(upto + 1):
                    val = comb[total_edges][d] * coef
                    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]

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

    # 中間頂点は 2..N-1 の N-2 個
    mid = N - 2

    # dp[(used, last_size)] = polynomial
    # used: すでに L1..Li に使った中間頂点数
    # last_size: 直前の層の頂点数
    dp = {(0, 1): [1] + [0] * R}  # L0 = {1}

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

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

            # L_layer は空であってはいけない
            for cur_size in range(1, remain + 1):
                ways_choose = C[remain][cur_size]
                terms = trans[prev_size][cur_size]

                npoly = multiply_by_terms(poly, terms)
                if ways_choose != 1:
                    npoly = [(x * ways_choose) % 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

        # LK に入れる中間頂点数を t とする
        for t in range(remain + 1):
            cur_size = t + 1  # +1 は頂点 N
            ways_choose = C[remain][t]

            # L_{K-1} と LK の間、かつ LK 内部
            terms1 = trans[prev_size][cur_size]
            poly2 = multiply_by_terms(poly, terms1)

            if ways_choose != 1:
                poly2 = [(x * ways_choose) % MOD for x in poly2]

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

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

            poly3 = multiply_by_terms(poly2, terms2)

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

    print(ans % MOD)


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