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

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

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

ソースコード

#include <iostream>
#include <vector>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using mint = modint998244353;

// 組み合わせ nCr の事前計算
mint C[500][500];
void init_C() {
    for (int i = 0; i < 500; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
}

int main() {
    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;
    if (target_E < K) {
        cout << 0 << endl;
        return 0;
    }

    // Poly[p][c][e] の事前計算
    // p: 前の層のサイズ, c: 今の層のサイズ, e: 追加される辺の数
    vector Poly(N + 1, vector(N + 1, vector<mint>(max_E + 1, 0)));
    for (int p = 1; p <= N; p++) {
        for (int c = 1; c <= N; c++) {
            int max_in = c * (c - 1) / 2;
            for (int e_in = 0; e_in <= max_in; e_in++) {
                mint w = C[max_in][e_in];
                
                // ((1+x)^p - 1)^c の x^k の係数を計算
                for (int j = 0; j <= c; j++) {
                    mint sign = ((c - j) % 2 == 1) ? -1 : 1;
                    mint ways_j = C[c][j] * sign;
                    for (int k = 0; k <= p * j; k++) {
                        int total_e = e_in + k;
                        if (total_e <= max_E) {
                            Poly[p][c][total_e] += w * ways_j * C[p * j][k];
                        }
                    }
                }
            }
        }
    }

    // dp[v][p][e]
    vector dp(N - 1, vector(N + 1, vector<mint>(max_E + 1, 0)));
    vector total_valid(N - 1, vector<mint>(max_E + 1, 0));
    
    dp[0][1][0] = 1; // v=0(プールから0個), p=1(頂点1のみ), e=0

    for (int step = 1; step <= N; step++) {
        vector next_dp(N - 1, vector(N + 1, vector<mint>(max_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].val() == 0) continue;

                    int remain = N - 2 - v;
                    // ステップKの場合は頂点Nが確定で入るため、プールから選ぶ数は0でもよい
                    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);
                        mint ways = C[remain][c_pool];
                        
                        int max_add = p * c_real + c_real * (c_real - 1) / 2;
                        for (int e_add = c_real; e_add <= max_add; e_add++) {
                            if (e + e_add > target_E) break;
                            if (Poly[p][c_real][e_add].val() == 0) continue;
                            
                            next_dp[v + c_pool][c_real][e + e_add] += dp[v][p][e] * ways * Poly[p][c_real][e_add];
                        }
                    }
                }
            }
        }
        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] += dp[v][p][e];
                    }
                }
            }
        }
    }

    mint 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) {
                ans += total_valid[v][e] * C[max_unreach_E][e_unreach];
            }
        }
    }

    cout << ans.val() << endl;
    return 0;
}