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

• 問題: No.3589 Make Ends Meet (Hard)
• ユーザー: marc2825
• 提出日時: 2026-06-09 13:10:27
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,986 bytes
• コンパイル時間: 1,306 ms
• コンパイル使用メモリ: 222,660 KB
• 実行使用メモリ: 27,520 KB
• 最終ジャッジ日時: 2026-07-10 21:00:32
• 合計ジャッジ時間: 5,255 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

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

using ll = long long;
const int MOD = 998244353;

using Poly = vector<int>;

Poly poly_mul(const Poly& a, const Poly& b, int E) {
    Poly res(E + 1, 0);

    for (int i = 0; i <= E; i++) {
        for (int j = 0; i + j <= E; j++) {
            res[i + j] = (res[i + j] + (ll)a[i] * b[j]) % MOD;
        }
    }

    return res;
}

void poly_add_scaled(Poly& dst, const Poly& src, int scale, int E) {
    for (int i = 0; i <= E; i++) {
        dst[i] = (dst[i] + (ll)src[i] * scale) % MOD;
    }
}

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

    int N, M, K;
    cin >> N >> M >> K;

    int E = N * (N - 1) / 2;
    int R = E - M;
    int S = N - 2;

    // 無効状態も全部回すため、free_edges が E を超える場合がある。
    int max_free_edges = S * N + S * (S - 1) / 2;
    int MAX = max(E, max_free_edges);

    // binomial coefficients
    vector<vector<int>> C(MAX + 1, vector<int>(MAX + 1, 0));

    for (int i = 0; i <= MAX; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            if (C[i][j] >= MOD) C[i][j] -= MOD;
        }
    }

    auto nCr = [&](int n, int r) -> int {
        if (r < 0 || r > n) return 0;
        return C[n][r];
    };

    // one_plus_pow[m] = (1+x)^m
    // 多項式としては x^E までだけ持つ。
    vector<Poly> one_plus_pow(MAX + 1, Poly(E + 1, 0));

    for (int m = 0; m <= MAX; m++) {
        for (int i = 0; i <= min(E, m); i++) {
            one_plus_pow[m][i] = C[m][i];
        }
    }

    // trans[b][c] =
    // ((1+x)^b - 1)^c * (1+x)^{c(c-1)/2}
    vector<vector<Poly>> trans(N + 1, vector<Poly>(N + 1, Poly(E + 1, 0)));

    for (int b = 0; b <= N; b++) {
        Poly base = one_plus_pow[b];
        base[0]--;
        if (base[0] < 0) base[0] += MOD;

        Poly power(E + 1, 0);
        power[0] = 1;

        for (int c = 0; c <= N; c++) {
            if (c > 0) {
                power = poly_mul(power, base, E);
            }

            int inside_edges = c * (c - 1) / 2;
            trans[b][c] = poly_mul(power, one_plus_pow[inside_edges], E);
        }
    }

    // dp[a][b]:
    // a = number of ordinary vertices used in L_1,...,L_j
    // b = size of current BFS layer L_j
    vector<vector<Poly>> dp(S + 1, vector<Poly>(N + 1, Poly(E + 1, 0)));

    // L_0 = {1}
    dp[0][1][0] = 1;

    for (int j = 0; j < K; j++) {
        vector<vector<Poly>> ndp(S + 1, vector<Poly>(N + 1, Poly(E + 1, 0)));

        bool last = (j + 1 == K);

        for (int a = 0; a <= S; a++) {
            int rem = S - a;

            for (int b = 0; b <= N; b++) {
                if (!last) {
                    // L_{j+1} contains only ordinary vertices.
                    for (int c = 1; c <= rem; c++) {
                        int ways = nCr(rem, c);
                        int a2 = a + c;

                        Poly tmp = poly_mul(dp[a][b], trans[b][c], E);
                        poly_add_scaled(ndp[a2][c], tmp, ways, E);
                    }
                } else {
                    // L_K must contain vertex N.
                    // If |L_K| = c, choose c-1 ordinary vertices.
                    for (int c = 1; c <= rem + 1; c++) {
                        int ways = nCr(rem, c - 1);
                        int a2 = a + c - 1;

                        Poly tmp = poly_mul(dp[a][b], trans[b][c], E);
                        poly_add_scaled(ndp[a2][c], tmp, ways, E);
                    }
                }
            }
        }

        dp.swap(ndp);
    }

    ll ans = 0;

    for (int a = 0; a <= S; a++) {
        int rem = S - a;

        for (int b = 0; b <= N; b++) {
            int free_edges = rem * b + rem * (rem - 1) / 2;

            Poly tmp = poly_mul(dp[a][b], one_plus_pow[free_edges], E);

            ans += tmp[R];
            ans %= MOD;
        }
    }

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