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

• 問題: No.3589 Make Ends Meet (Hard)
• ユーザー: marc2825
• 提出日時: 2026-06-09 14:25:44
• 言語: PyPy3 (7.3.17)
• 結果: TLE
• 実行時間: -
• コード長: 5,756 bytes
• コンパイル時間: 232 ms
• コンパイル使用メモリ: 96,104 KB
• 実行使用メモリ: 165,344 KB
• 最終ジャッジ日時: 2026-07-10 21:00:42
• 合計ジャッジ時間: 6,511 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

ソースコード

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])
    
    MOD = 998244353
    
    # グラフに残すべき辺の数
    E_target = N * (N - 1) // 2 - M
    
    # K本の辺がなければ距離Kのパスは作れない
    if E_target < K:
        print(0)
        return
        
    # パスカルの三角形による組み合わせ計算の事前構築
    MAX_COMB = 610
    COMB = [[0] * MAX_COMB for _ in range(MAX_COMB)]
    for i in range(MAX_COMB):
        COMB[i][0] = 1
        for j in range(1, i + 1):
            COMB[i][j] = (COMB[i-1][j-1] + COMB[i-1][j]) % MOD
            
    # W[p][s][k]: サイズ p のレイヤーとサイズ s のレイヤーの間に、
    # 各 s 側の頂点が少なくとも1本の辺を持つようにちょうど k 本の辺を張る組み合わせ
    W = [[[0 for _ in range(p * s + 1)] for s in range(N + 1)] for p in range(N + 1)]
    for p in range(1, N + 1):
        poly1 = [0] * (p + 1)
        for j in range(1, p + 1):
            poly1[j] = COMB[p][j]
            
        W[p][1] = poly1 + [0] * 0
        for s in range(2, N + 1):
            prev = W[p][s-1]
            curr = [0] * (p * s + 1)
            for j in range(s - 1, p * (s - 1) + 1):
                if prev[j] == 0: continue
                for k in range(1, p + 1):
                    curr[j + k] = (curr[j + k] + prev[j] * poly1[k]) % MOD
            W[p][s] = curr
            
    # Cost_nonzero[p][s]: p -> s の遷移において、内部辺も含めて e_add 本の辺を張る組み合わせ数
    # (計算の高速化のため、組み合わせが 0 より大きいものだけを保持)
    Cost_nonzero = [[[ ] for _ in range(N + 1)] for _ in range(N + 1)]
    for p in range(1, N + 1):
        for s in range(1, N + 1):
            max_j = s * (s - 1) // 2
            temp_cost = [0] * (max_j + p * s + 1)
            for j in range(max_j + 1):
                ways_in = COMB[max_j][j]
                if ways_in == 0: continue
                for k in range(s, p * s + 1):
                    ways_between = W[p][s][k]
                    if ways_between == 0: continue
                    temp_cost[j + k] = (temp_cost[j + k] + ways_in * ways_between) % MOD
            
            for e_add, ways in enumerate(temp_cost):
                if ways > 0:
                    Cost_nonzero[p][s].append((e_add, ways))

    # DPテーブル: dp[使用した"その他の頂点"の数][直前レイヤーのサイズ][これまでに使った辺の数]
    dp = [[[0] * (E_target + 1) for _ in range(N + 1)] for _ in range(N - 1)]
    dp[0][1][0] = 1 # 初期状態：レイヤー0（頂点1のみ）、使用辺0
    
    active_states = [(0, 1, 0)]
    ans_states = [[0] * (E_target + 1) for _ in range(N - 1)]
    
    # 距離 1 から N-1 までのレイヤーを順番に構築
    for i in range(1, N):
        next_dp = [[[0] * (E_target + 1) for _ in range(N + 1)] for _ in range(N - 1)]
        
        for v, p, e in active_states:
            count = dp[v][p][e]
            limit_c = N - 2 - v
            
            # c: レイヤー i に配置する "その他の頂点" の数
            for c in range(limit_c + 1):
                # i == K のときは頂点 N が必ず入るためサイズが +1 される
                s = c + 1 if i == K else c
                
                # レイヤーのサイズが 0 になった場合は探索打ち切り
                if s == 0:
                    # 距離 K を超えていれば有効な終了状態として保存
                    if i > K:
                        ans_states[v][e] = (ans_states[v][e] + count) % MOD
                    continue
                    
                comb_v = COMB[limit_c][c]
                base_ways = (count * comb_v) % MOD
                
                nxt_v = v + c
                p_s_nonzero = Cost_nonzero[p][s]
                
                # 今回のレイヤー構築で消費する辺の数の遷移
                for idx in range(len(p_s_nonzero)):
                    e_add, ways = p_s_nonzero[idx]
                    nxt_e = e + e_add
                    
                    if nxt_e > E_target:
                        break # e_addは昇順なので、超過したら終了
                    
                    next_dp[nxt_v][s][nxt_e] = (next_dp[nxt_v][s][nxt_e] + base_ways * ways) % MOD
                    
        dp = next_dp
        active_states = []
        for _v in range(N - 1):
            for _p in range(N + 1):
                for _e in range(E_target + 1):
                    if dp[_v][_p][_e] > 0:
                        active_states.append((_v, _p, _e))
                        
    # N-1番目のレイヤーまで到達した（もしくはそこで終わった）状態を合流させる
    for v, p, e in active_states:
        ans_states[v][e] = (ans_states[v][e] + dp[v][p][e]) % MOD
        
    final_ans = 0
    # 未到達レイヤー( L_infty ) 内での辺の張り方の組み合わせを計算
    for v in range(N - 1):
        U = N - 2 - v # 未到達となる "その他の頂点" の数
        max_U_edges = U * (U - 1) // 2
        
        for e in range(E_target + 1):
            if ans_states[v][e] == 0: continue
            
            rem_e = E_target - e # L_infty 内で張るべき残り辺の数
            if 0 <= rem_e <= max_U_edges:
                ways = COMB[max_U_edges][rem_e]
                final_ans = (final_ans + ans_states[v][e] * ways) % MOD
                
    print(final_ans)

if __name__ == '__main__':
    solve()