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

• 問題: No.3589 Make Ends Meet (Hard)
• ユーザー: marc2825
• 提出日時: 2026-06-13 16:44:50
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,449 bytes
• コンパイル時間: 1,315 ms
• コンパイル使用メモリ: 221,432 KB
• 実行使用メモリ: 7,808 KB
• 最終ジャッジ日時: 2026-07-10 21:02:18
• 合計ジャッジ時間: 5,313 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    int total_edges = N * (N - 1) / 2;
    int rem_edges = total_edges - M;

    if (rem_edges < 0) {
        cout << 0 << '\n';
        return 0;
    }

    int MAX_C = max(total_edges + 1, N + 1);
    vector<vector<long long>> C(MAX_C, vector<long long>(MAX_C, 0));

    for (int i = 0; i < MAX_C; 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 UMAX = N;
    int SMAX = N;
    int EMAX = rem_edges;

    auto idx = [&](int prev_sz, int u, int e) {
        return (prev_sz * (UMAX + 1) + u) * (EMAX + 1) + e;
    };

    int SZ = (SMAX + 1) * (UMAX + 1) * (EMAX + 1);

    vector<long long> curr(SZ, 0), nxt(SZ, 0);

    // 状態: dp[prev_sz][u][e]
    curr[idx(1, 0, 0)] = 1;

    for (int d = 1; d <= K; d++) {
        fill(nxt.begin(), nxt.end(), 0);

        for (int prev_sz = 0; prev_sz <= SMAX; prev_sz++) {
            for (int u = 0; u <= UMAX; u++) {
                for (int e = 0; e <= EMAX; e++) {
                    long long ways = curr[idx(prev_sz, u, e)];
                    if (ways == 0) continue;

                    int rem_v = (N - 2) - u;
                    if (rem_v < 0) continue;

                    int min_vars = 0;
                    int max_vars = rem_v;

                    if (d != K) {
                        min_vars = max(min_vars, 1);
                    }

                    for (int k_vars = min_vars; k_vars <= max_vars; k_vars++) {
                        int sz = k_vars + (d == K ? 1 : 0);
                        if (sz == 0) continue;

                        long long v_choices = C[rem_v][k_vars];
                        if (v_choices == 0) continue;

                        // 直前の層 prev_sz との接続の組合せ
                        // 各頂点1本以上
                        vector<long long> ways_to_connect(prev_sz + 1, 0);
                        for (int j = 1; j <= prev_sz; j++) {
                            ways_to_connect[j] = C[prev_sz][j];
                        }

                        vector<long long> sz_conn(prev_sz * sz + 1, 0);
                        sz_conn[0] = 1;

                        for (int rep = 0; rep < sz; rep++) {
                            vector<long long> next_sz_conn(sz_conn.size(), 0);

                            for (int e1 = 0; e1 < (int)sz_conn.size(); e1++) {
                                if (sz_conn[e1] == 0) continue;

                                for (int e2 = 1; e2 <= prev_sz; e2++) {
                                    if (e1 + e2 < (int)next_sz_conn.size()) {
                                        next_sz_conn[e1 + e2] += sz_conn[e1] * ways_to_connect[e2];
                                        next_sz_conn[e1 + e2] %= MOD;
                                    }
                                }
                            }

                            sz_conn = next_sz_conn;
                        }

                        // 同一層内の辺
                        int inner_max = sz * (sz - 1) / 2;
                        vector<long long> ways_inner(inner_max + 1, 0);
                        for (int i = 0; i <= inner_max; i++) {
                            ways_inner[i] = C[inner_max][i];
                        }

                        long long base_ways = ways * v_choices % MOD;

                        for (int e_conn = 0; e_conn < (int)sz_conn.size(); e_conn++) {
                            long long w_conn = sz_conn[e_conn];
                            if (w_conn == 0) continue;

                            for (int e_inner = 0; e_inner < (int)ways_inner.size(); e_inner++) {
                                long long w_inner = ways_inner[e_inner];

                                int added_edges = e_conn + e_inner;
                                if (e + added_edges > rem_edges) continue;

                                int n_u = u + k_vars;
                                int n_e = e + added_edges;

                                long long n_ways = base_ways * w_conn % MOD;
                                n_ways = n_ways * w_inner % MOD;

                                int id = idx(sz, n_u, n_e);
                                nxt[id] += n_ways;
                                nxt[id] %= MOD;
                            }
                        }
                    }
                }
            }
        }

        curr.swap(nxt);
    }

    long long ans = 0;

    for (int prev_sz = 0; prev_sz <= SMAX; prev_sz++) {
        for (int u = 0; u <= UMAX; u++) {
            for (int e = 0; e <= EMAX; e++) {
                long long ways = curr[idx(prev_sz, u, e)];
                if (ways == 0) continue;

                int rem_v_final = (N - 2) - u;
                if (rem_v_final < 0) continue;

                int free_edges =
                    rem_v_final * (rem_v_final - 1) / 2
                    + prev_sz * rem_v_final;

                int needed = rem_edges - e;

                if (0 <= needed && needed <= free_edges) {
                    ans += ways * C[free_edges][needed] % MOD;
                    ans %= MOD;
                }
            }
        }
    }

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