#1168719 (C++17) No.3589 Make Ends Meet (Hard)

• 問題: No.3589 Make Ends Meet (Hard)
• ユーザー: marc2825
• 提出日時: 2026-06-09 03:59:20
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: RE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 5,533 bytes
• コンパイル時間: 767 ms
• コンパイル使用メモリ: 110,492 KB
• 実行使用メモリ: 16,512 KB
• 最終ジャッジ日時: 2026-07-10 20:59:53
• 合計ジャッジ時間: 5,006 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 2 RE * 1
other	AC * 40 RE * 7

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long MOD = 998244353;

// 組み合わせ nCr の事前計算 (最大 1000 まで確保して配列外参照を防ぐ)
long long C[1005][1005];
void init_C() {
    for (int i = 0; i <= 1000; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
}

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    init_C();
    int N, M, K;
    if (!(cin >> N >> M >> K)) return 0;

    int max_E = N * (N - 1) / 2;
    int target_E = max_E - M;
    
    // 構成すべき最短距離 K が残すべき辺の数より大きい場合、到達不可能
    if (target_E < K) {
        cout << 0 << "\n";
        return 0;
    }

    // Poly[p][c][e] の事前計算
    // p: 前の層のサイズ, c: 今の層のサイズ, e: 追加される辺の数
    vector<vector<vector<long long>>> Poly(N + 1, vector<vector<long long>>(N + 1, vector<long long>(target_E + 1, 0)));
    
    for (int p = 1; p <= N; p++) {
        for (int c = 1; c <= N; c++) {
            // ((1+x)^p - 1)^c の x^k の係数を B[k] として先に計算 (O(c * target_E)に落とす)
            vector<long long> B(target_E + 1, 0);
            for (int k = 0; k <= target_E; k++) {
                for (int j = 0; j <= c; j++) {
                    // p * j < k の場合は組み合わせが0になるためスキップ
                    if (p * j < k) continue; 

                    long long sign = ((c - j) % 2 == 1) ? -1 : 1;
                    long long ways_j = (C[c][j] * sign) % MOD;
                    if (ways_j < 0) ways_j += MOD;
                    
                    long long term = (ways_j * C[p * j][k]) % MOD;
                    B[k] = (B[k] + term) % MOD;
                }
            }

            // (1+x)^{c(c-1)/2} と B(x) を畳み込む
            int max_in = c * (c - 1) / 2;
            for (int total_e = 0; total_e <= target_E; total_e++) {
                for (int e_in = 0; e_in <= min(total_e, max_in); e_in++) {
                    int k = total_e - e_in;
                    long long ways_in = C[max_in][e_in];
                    long long term = (ways_in * B[k]) % MOD;
                    Poly[p][c][total_e] = (Poly[p][c][total_e] + term) % MOD;
                }
            }
        }
    }

    // dp[v][p][e]
    // v: プール(N-2個の頂点)から使った数, p: 直前の層のサイズ, e: 使った辺の総数
    vector<vector<vector<long long>>> dp(N - 1, vector<vector<long long>>(N + 1, vector<long long>(target_E + 1, 0)));
    vector<vector<long long>> total_valid(N - 1, vector<long long>(target_E + 1, 0));
    
    dp[0][1][0] = 1; // 頂点1のみの層 (v=0, p=1, e=0)

    for (int step = 1; step <= N; step++) {
        vector<vector<vector<long long>>> next_dp(N - 1, vector<vector<long long>>(N + 1, vector<long long>(target_E + 1, 0)));
        bool is_K = (step == K);

        for (int v = 0; v <= N - 2; v++) {
            for (int p = 1; p <= N; p++) {
                for (int e = 0; e <= target_E; e++) {
                    if (dp[v][p][e] == 0) continue;

                    int remain = N - 2 - v;
                    // ステップKの時は、プールからの頂点が0個でも「頂点N」が含まれるため有効
                    int start_c = is_K ? 0 : 1;
                    
                    for (int c_pool = start_c; c_pool <= remain; c_pool++) {
                        int c_real = c_pool + (is_K ? 1 : 0);
                        long long ways = C[remain][c_pool];
                        
                        // 辺の追加数の範囲を絞って遷移
                        for (int e_add = c_real; e_add <= target_E - e; e_add++) {
                            if (Poly[p][c_real][e_add] == 0) continue;
                            
                            long long add_val = (dp[v][p][e] * ways) % MOD;
                            add_val = (add_val * Poly[p][c_real][e_add]) % MOD;
                            
                            next_dp[v + c_pool][c_real][e + e_add] = (next_dp[v + c_pool][c_real][e + e_add] + add_val) % MOD;
                        }
                    }
                }
            }
        }
        dp = next_dp;
        
        // K層目以降に到達したグラフは「有効な到達可能成分」として結果に足し込む
        if (step >= K) {
            for (int v = 0; v <= N - 2; v++) {
                for (int p = 1; p <= N; p++) {
                    for (int e = 0; e <= target_E; e++) {
                        total_valid[v][e] = (total_valid[v][e] + dp[v][p][e]) % MOD;
                    }
                }
            }
        }
    }

    long long ans = 0;
    
    // 到達不能な頂点集合 U 内部の辺の選び方を掛けて集計
    for (int v = 0; v <= N - 2; v++) {
        int U = N - 2 - v;
        int max_unreach_E = U * (U - 1) / 2;
        
        for (int e = 0; e <= target_E; e++) {
            int e_unreach = target_E - e;
            // 未到達成分の辺の数として妥当か判定
            if (e_unreach >= 0 && e_unreach <= max_unreach_E) {
                long long ways = C[max_unreach_E][e_unreach];
                long long add_val = (total_valid[v][e] * ways) % MOD;
                ans = (ans + add_val) % MOD;
            }
        }
    }

    cout << ans << "\n";
    return 0;
}