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

• 問題: No.3589 Make Ends Meet (Hard)
• ユーザー: marc2825
• 提出日時: 2026-05-29 17:31:07
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 230 ms / 2,000 ms
• コード長: 3,724 bytes
• コンパイル時間: 1,294 ms
• コンパイル使用メモリ: 221,072 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-07-10 20:55:51
• 合計ジャッジ時間: 4,682 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const int MOD = 998244353;

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int eval_at(int N, int K, int x, const vector<vector<int>>& C) {
    int E = N * (N - 1) / 2;
    int S = N - 2;
    int q = x + 1;
    if (q >= MOD) q -= MOD;

    vector<int> qpow(E + 1, 1);
    for (int i = 1; i <= E; i++) qpow[i] = (ll)qpow[i - 1] * q % MOD;

    vector<vector<int>> pow_qs_minus_1(S + 2, vector<int>(S + 1, 1));
    for (int s = 0; s <= S + 1; s++) {
        int w = qpow[s] - 1;
        if (w < 0) w += MOD;
        for (int t = 1; t <= S; t++) {
            pow_qs_minus_1[s][t] = (ll)pow_qs_minus_1[s][t - 1] * w % MOD;
        }
    }

    vector<vector<int>> dp(S + 1, vector<int>(S + 2, 0));
    dp[S][1] = 1;

    for (int step = 0; step < K - 1; step++) {
        vector<vector<int>> ndp(S + 1, vector<int>(S + 2, 0));
        for (int r = 0; r <= S; r++) {
            for (int s = 0; s <= S + 1; s++) {
                int cur = dp[r][s];
                if (!cur) continue;
                for (int t = 0; t <= r; t++) {
                    ll add = cur;
                    add = add * C[r][t] % MOD;
                    add = add * pow_qs_minus_1[s][t] % MOD;
                    add = add * qpow[t * (t - 1) / 2] % MOD;
                    ndp[r - t][t] += add;
                    if (ndp[r - t][t] >= MOD) ndp[r - t][t] -= MOD;
                }
            }
        }
        dp.swap(ndp);
    }

    ll ans = 0;
    for (int r = 0; r <= S; r++) {
        for (int s = 0; s <= S + 1; s++) {
            int cur = dp[r][s];
            if (!cur) continue;
            int factor = qpow[s] - 1;
            if (factor < 0) factor += MOD;
            int base = s * r + r + r * (r - 1) / 2;
            ans += (ll)cur * factor % MOD * qpow[base] % MOD;
            ans %= MOD;
        }
    }
    return (int)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;
    int R = E - M;

    vector<vector<int>> C(N + 2, vector<int>(N + 2, 0));
    for (int i = 0; i <= N + 1; 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;
        }
    }

    vector<int> vals(E + 1);
    for (int x = 0; x <= E; x++) vals[x] = eval_at(N, K, x, C);

    // Newton interpolation on points 0,1,...,E:
    // P(x)=sum_k diff[k] * binom(x,k).
    vector<int> diff = vals;
    for (int k = 0; k <= E; k++) {
        for (int i = E; i > k; i--) {
            diff[i] -= diff[i - 1];
            if (diff[i] < 0) diff[i] += MOD;
        }
    }

    vector<int> inv(E + 2, 1);
    for (int i = 1; i <= E + 1; i++) inv[i] = (int)modpow(i, MOD - 2);

    vector<int> basis(1, 1); // binom(x,0)
    ll answer = 0;
    for (int k = 0; k <= E; k++) {
        if (R < (int)basis.size()) {
            answer += (ll)diff[k] * basis[R] % MOD;
            answer %= MOD;
        }
        if (k == E) break;
        // basis <- basis * (x-k)/(k+1)
        vector<int> nbasis(basis.size() + 1, 0);
        for (int i = 0; i < (int)basis.size(); i++) {
            nbasis[i] = (nbasis[i] - (ll)basis[i] * k) % MOD;
            if (nbasis[i] < 0) nbasis[i] += MOD;
            nbasis[i + 1] += basis[i];
            if (nbasis[i + 1] >= MOD) nbasis[i + 1] -= MOD;
        }
        int invk = inv[k + 1];
        for (int &v : nbasis) v = (ll)v * invk % MOD;
        basis.swap(nbasis);
    }

    cout << answer % MOD << '\n';
    return 0;
}