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

• 問題: No.3589 Make Ends Meet (Hard)
• ユーザー: marc2825
• 提出日時: 2026-05-30 09:44:43
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 967 ms / 2,000 ms
• コード長: 6,973 bytes
• コンパイル時間: 1,705 ms
• コンパイル使用メモリ: 242,840 KB
• 実行使用メモリ: 8,448 KB
• 最終ジャッジ日時: 2026-07-10 20:58:53
• 合計ジャッジ時間: 5,482 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 47

ソースコード

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

using ll = long long;

static const int MOD = 998244353;

int addmod(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

int submod(int a, int b) {
    a -= b;
    if (a < 0) a += MOD;
    return a;
}

int mulmod(ll a, ll b) {
    return int(a * b % MOD);
}

int brute(int N, int M, int K) {
    vector<pair<int,int>> edges;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            edges.push_back({i, j});
        }
    }

    int E = edges.size();
    int R = E - M;

    if (E > 62) return -1;

    unsigned long long LIM = 1ULL << E;
    int ans = 0;

    for (unsigned long long mask = 0; mask < LIM; mask++) {
        // mask = 残す辺集合
        if (__builtin_popcountll(mask) != R) continue;

        vector<vector<int>> G(N);
        for (int e = 0; e < E; e++) {
            if ((mask >> e) & 1ULL) {
                auto [u, v] = edges[e];
                G[u].push_back(v);
                G[v].push_back(u);
            }
        }

        vector<int> dist(N, -1);
        queue<int> q;
        dist[0] = 0;
        q.push(0);

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (int to : G[v]) {
                if (dist[to] == -1) {
                    dist[to] = dist[v] + 1;
                    q.push(to);
                }
            }
        }

        if (dist[N - 1] == K) {
            ans++;
            if (ans >= MOD) ans -= MOD;
        }
    }

    return ans;
}

vector<int> multiply_poly_terms(const vector<int>& poly, const vector<pair<int,int>>& terms, int R) {
    vector<int> res(R + 1, 0);

    for (int i = 0; i <= R; i++) {
        if (poly[i] == 0) continue;

        for (auto [d, b] : terms) {
            if (i + d > R) break;
            res[i + d] = (res[i + d] + (ll)poly[i] * b) % MOD;
        }
    }

    return res;
}

int solve_fast(int N, int M, int K) {
    int E = N * (N - 1) / 2;
    int R = E - M;

    if (R < 0) return 0;

    // comb[n][r], n <= E, r <= R
    vector<vector<int>> comb(E + 1, vector<int>(R + 1, 0));
    for (int i = 0; i <= E; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= min(i, R); j++) {
            if (j == i) comb[i][j] = 1;
            else comb[i][j] = addmod(comb[i - 1][j - 1], comb[i - 1][j]);
        }
    }

    // 頂点選択用 C[n][r]
    vector<vector<int>> C(N + 1, vector<int>(N + 1, 0));
    for (int i = 0; i <= N; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = addmod(C[i - 1][j - 1], C[i - 1][j]);
        }
    }

    auto one_plus_x_pow = [&](int t) {
        vector<pair<int,int>> terms;
        for (int i = 0; i <= min(t, R); i++) {
            if (comb[t][i]) terms.push_back({i, comb[t][i]});
        }
        return terms;
    };

    // trans[p][q]:
    // 直前層サイズ p、現在層サイズ q の遷移多項式
    //
    // 現在層内部の辺は自由
    // 現在層の各頂点は直前層へ少なくとも 1 本辺を持つ
    vector<vector<vector<pair<int,int>>>> trans(
        N + 1,
        vector<vector<pair<int,int>>>(N + 1)
    );

    for (int p = 1; p <= N; p++) {
        for (int q = 1; q <= N; q++) {
            if (p + q > N) continue;

            int inside = q * (q - 1) / 2;
            vector<int> arr(R + 1, 0);

            // (1+x)^inside * ((1+x)^p - 1)^q
            // = sum_{r=0}^{q} (-1)^{q-r} C(q,r) (1+x)^{inside + p*r}
            for (int r = 0; r <= q; r++) {
                int coef = C[q][r];
                bool plus = ((q - r) % 2 == 0);
                int total = inside + p * r;

                for (int d = 0; d <= min(total, R); d++) {
                    int val = mulmod(coef, comb[total][d]);
                    if (plus) arr[d] = addmod(arr[d], val);
                    else arr[d] = submod(arr[d], val);
                }
            }

            for (int i = 0; i <= R; i++) {
                if (arr[i]) trans[p][q].push_back({i, arr[i]});
            }
        }
    }

    int mid = N - 2;

    // key = used * (N+1) + last_size
    // used: 中間頂点 2..N-1 のうち、すでに距離層に使った数
    // last_size: 直前の距離層サイズ
    map<pair<int,int>, vector<int>> dp;
    dp[{0, 1}] = vector<int>(R + 1, 0);
    dp[{0, 1}][0] = 1;

    // L1, L2, ..., L_{K-1}
    for (int layer = 1; layer <= K - 1; layer++) {
        map<pair<int,int>, vector<int>> ndp;

        for (auto& it : dp) {
            auto [used, prev_size] = it.first;
            const vector<int>& poly = it.second;

            int remain = mid - used;

            for (int cur_size = 1; cur_size <= remain; cur_size++) {
                if (trans[prev_size][cur_size].empty()) continue;

                int ways = C[remain][cur_size];

                vector<int> npoly = multiply_poly_terms(
                    poly,
                    trans[prev_size][cur_size],
                    R
                );

                if (ways != 1) {
                    for (int& x : npoly) x = mulmod(x, ways);
                }

                pair<int,int> key = {used + cur_size, cur_size};

                if (!ndp.count(key)) {
                    ndp[key] = move(npoly);
                } else {
                    for (int i = 0; i <= R; i++) {
                        ndp[key][i] = addmod(ndp[key][i], npoly[i]);
                    }
                }
            }
        }

        dp.swap(ndp);
    }

    int ans = 0;

    // LK には頂点 N が必ず入る
    for (auto& it : dp) {
        auto [used, prev_size] = it.first;
        const vector<int>& poly = it.second;

        int remain = mid - used;

        // t = LK に追加で入れる中間頂点数
        for (int t = 0; t <= remain; t++) {
            int cur_size = t + 1; // +1 は頂点 N

            if (trans[prev_size][cur_size].empty()) continue;

            int ways = C[remain][t];

            vector<int> poly2 = multiply_poly_terms(
                poly,
                trans[prev_size][cur_size],
                R
            );

            if (ways != 1) {
                for (int& x : poly2) x = mulmod(x, ways);
            }

            // B は距離 K より大きい、または到達不能な頂点
            int b = remain - t;

            // B 内部の辺と、B - LK 間の辺は自由
            int free_edges = b * (b - 1) / 2 + b * cur_size;

            vector<pair<int,int>> free_terms = one_plus_x_pow(free_edges);

            vector<int> poly3 = multiply_poly_terms(poly2, free_terms, R);

            ans = addmod(ans, poly3[R]);
        }
    }

    return ans;
}

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

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

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

    if (E <= 22) {
        cout << brute(N, M, K) << '\n';
    } else {
        cout << solve_fast(N, M, K) << '\n';
    }

    return 0;
}