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

• 問題: No.3589 Make Ends Meet (Hard)
• ユーザー: marc2825
• 提出日時: 2026-06-09 14:24:05
• 言語: PyPy3 (7.3.17)
• 結果: TLE
• 実行時間: -
• コード長: 5,554 bytes
• コンパイル時間: 233 ms
• コンパイル使用メモリ: 96,108 KB
• 実行使用メモリ: 105,000 KB
• 最終ジャッジ日時: 2026-07-10 21:00:40
• 合計ジャッジ時間: 12,609 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 46 TLE * 1

ソースコード

import sys

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])

    # 残すべき辺の数
    E_target = N * (N - 1) // 2 - M
    if E_target < 0:
        print(0)
        return

    MOD = 998244353

    # 多項式のかけ算（E_target 次までで打ち切ることで高速化）
    def poly_mul(A, B):
        if not A or not B: return []
        res_len = min(E_target + 1, len(A) + len(B) - 1)
        res = [0] * res_len
        for i in range(len(A)):
            if A[i] == 0: continue
            a = A[i]
            max_j = min(len(B), res_len - i)
            for j in range(max_j):
                res[i+j] = (res[i+j] + a * B[j]) % MOD
        return res

    # 多項式の累乗
    def poly_pow(A, p):
        res = [1]
        base = A[:]
        while p > 0:
            if p % 2 == 1:
                res = poly_mul(res, base)
            base = poly_mul(base, base)
            p //= 2
        return res

    # 二項係数の事前計算
    C = [[0] * 600 for _ in range(600)]
    for i in range(600):
        C[i][0] = 1
        for j in range(1, i + 1):
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD

    # 階乗とその逆元の事前計算
    fact = [1] * (N + 1)
    inv_fact = [1] * (N + 1)
    for i in range(1, N + 1):
        fact[i] = (fact[i-1] * i) % MOD
    inv_fact[N] = pow(fact[N], MOD - 2, MOD)
    for i in range(N - 1, -1, -1):
        inv_fact[i] = (inv_fact[i+1] * (i + 1)) % MOD

    # T_poly[c_prev][c]: 直前のサイズ c_prev, 今回のサイズ c のレイヤー間の辺の母関数
    T_poly = [[[] for _ in range(N + 1)] for _ in range(N + 1)]
    for c_prev in range(1, N + 1):
        base = [0] * (c_prev + 1)
        for i in range(1, c_prev + 1):
            base[i] = C[c_prev][i]
        
        for c in range(1, N + 1):
            p1 = poly_pow(base, c)
            edges_internal = c * (c - 1) // 2
            p2 = [0] * (edges_internal + 1)
            for i in range(edges_internal + 1):
                p2[i] = C[edges_internal][i]
            T_poly[c_prev][c] = poly_mul(p1, p2)

    # dp[i][c_prev][S] = 母関数（配列）
    dp = [[[[ ] for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(K + 1)]
    dp[0][1][1] = [1]  # レイヤー0: サイズ1 (頂点1), 総頂点1, 辺0

    # 距離 K までのレイヤーを構築
    for i in range(K):
        for S in range(1, N):
            for c_prev in range(1, S + 1):
                if not dp[i][c_prev][S]: continue
                for c in range(1, N - S + 1):
                    poly_T = T_poly[c_prev][c]
                    res = poly_mul(dp[i][c_prev][S], poly_T)
                    if not res: continue
                    
                    # 頂点Nが属するK番目のレイヤーの係数調整
                    if i + 1 == K:
                        w = inv_fact[c-1]
                    else:
                        w = inv_fact[c]
                        
                    for idx in range(len(res)):
                        res[idx] = (res[idx] * w) % MOD
                    
                    # 遷移先へ加算
                    target = dp[i+1][c][S+c]
                    if len(target) < len(res):
                        target.extend([0] * (len(res) - len(target)))
                    for idx in range(len(res)):
                        target[idx] = (target[idx] + res[idx]) % MOD

    # 距離 K に到達した後の、任意の長さの追加レイヤー処理用 DP
    dp_after = [[[] for _ in range(N + 1)] for _ in range(N + 1)]
    for S in range(1, N + 1):
        for c in range(1, S + 1):
            dp_after[c][S] = dp[K][c][S][:]

    # 以降のレイヤーを追加（S を昇順にループすることで順次構築）
    for S in range(1, N):
        for c_prev in range(1, S + 1):
            if not dp_after[c_prev][S]: continue
            for c in range(1, N - S + 1):
                poly_T = T_poly[c_prev][c]
                res = poly_mul(dp_after[c_prev][S], poly_T)
                if not res: continue
                
                w = inv_fact[c]
                for idx in range(len(res)):
                    res[idx] = (res[idx] * w) % MOD
                
                target = dp_after[c][S+c]
                if len(target) < len(res):
                    target.extend([0] * (len(res) - len(target)))
                for idx in range(len(res)):
                    target[idx] = (target[idx] + res[idx]) % MOD

    # 到達不能な頂点集合 U の処理
    total_ans = []
    for S in range(1, N + 1):
        for c in range(1, S + 1):
            if not dp_after[c][S]: continue
            U = N - S
            U_edges = U * (U - 1) // 2
            U_poly = [0] * (U_edges + 1)
            w = inv_fact[U]
            for idx in range(U_edges + 1):
                U_poly[idx] = (C[U_edges][idx] * w) % MOD
            
            res = poly_mul(dp_after[c][S], U_poly)
            if len(total_ans) < len(res):
                total_ans.extend([0] * (len(res) - len(total_ans)))
            for idx in range(len(res)):
                total_ans[idx] = (total_ans[idx] + res[idx]) % MOD

    # 目的の辺の数の係数を取り出し、ラベル付けの順列を掛ける
    ans = 0
    if E_target < len(total_ans):
        ans = total_ans[E_target]

    ans = (ans * fact[N-2]) % MOD
    print(ans)

if __name__ == '__main__':
    solve()