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

• 問題: No.3589 Make Ends Meet (Hard)
• ユーザー: 👑 potato167
• 提出日時: 2026-07-10 23:00:17
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 529 ms / 2,000 ms
• コード長: 4,172 bytes
• コンパイル時間: 1,644 ms
• コンパイル使用メモリ: 233,500 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-07-10 23:00:30
• 合計ジャッジ時間: 8,757 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

ソースコード

#line 1 "f.cpp"
// https://atcoder.jp/contests/abc389/submissions/61843132
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
#include <atcoder/modint>
using mint = atcoder::modint998244353;

namespace po167{
template<class T>
struct Binomial{
    std::vector<T> fact_vec, fact_inv_vec;
    void extend(int m = -1){
        int n = fact_vec.size();
        if (m == -1) m = n * 2;
        if (n >= m) return;
        fact_vec.resize(m);
        fact_inv_vec.resize(m);
        for (int i = n; i < m; i++){
            fact_vec[i] = fact_vec[i - 1] * T(i);
        }
        fact_inv_vec[m - 1] = T(1) / fact_vec[m - 1];
        for (int i = m - 1; i > n; i--){
            fact_inv_vec[i - 1] = fact_inv_vec[i] * T(i);
        }
    }
    Binomial(int MAX = 0){
        fact_vec.resize(1, T(1));
        fact_inv_vec.resize(1, T(1));
        extend(MAX + 1);
    }

    T fact(int i){
        if (i < 0) return 0;
        while (int(fact_vec.size()) <= i) extend();
        return fact_vec[i];
    }
    T invfact(int i){
        if (i < 0) return 0;
        while (int(fact_inv_vec.size()) <= i) extend();
        return fact_inv_vec[i];
    }
    T C(int a, int b){
        if (a < b || b < 0) return 0;
        return fact(a) * invfact(b) * invfact(a - b);
    }
};
}

// https://ferin-tech.hatenablog.com/entry/2019/08/11/ラグランジュ補間
// x座標が相異なるn+1点(x_i,y_i)を通るn次以下の多項式f(x)を返す
// O(n^2)
#define REP(i, a) for (int i = 0; i < a; i++)
#define FOR(i, a, b) rep(i, a, b)
vector<mint> lagrange_interpolation(vector<mint> x, vector<mint> y) {
    const ll n = x.size() - 1;
    REP(i, n+1) {
        mint t = 1;
        REP(j, n+1) if(i != j) t *= x[i]-x[j];
        y[i] /= t;
    }
    ll cur = 0, nxt = 1;
    vector<vector<mint>> dp(2, vector<mint>(n+2));
    dp[0][0] = -1 * x[0], dp[0][1] = 1;
    FOR(i, 1, n+1) {
        REP(j, n+2) {
            dp[nxt][j] = dp[cur][j] * -1 * x[i];
            if(j >= 1) dp[nxt][j] += dp[cur][j-1];
        }
        swap(nxt, cur);
    }
    vector<mint> xinv(n+1);
    REP(i, n+1) xinv[i] = x[i].inv();
    vector<mint> ret(n+1);  // f(x)
    REP(i, n+1) {
        if(y[i]==0) continue;
        // 0割り対策の場合分け
        if(x[i] == 0) {
            REP(j, n+1) ret[j] += dp[cur][j+1] * y[i];
        } else {
            ret[0] -= dp[cur][0] * xinv[i] * y[i];
            mint pre = -1 * dp[cur][0] * xinv[i];
            FOR(j, 1, n+1) {
                ret[j] -= (dp[cur][j] - pre) * xinv[i] * y[i];
                pre = -1 * (dp[cur][j] - pre) * xinv[i];
            }
        }
    }
    return ret;
}

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

    int N, M, K;
    cin >> N >> M >> K;
    po167::Binomial<mint> table(N);
    int D = N * (N - 1) / 2;
    vector<mint> ans(D + 1);
    rep(rp, 0, D + 1) {
        vector dp(N + 1, vector(N + 1, vector<mint>(N + 1)));
        dp[1][1][0] = 1;
        vector<mint> p2(N * N + 1, 1);
        rep(i, 0, N * N) p2[i + 1] = p2[i] * (rp + 2);
        vector p3(N, vector<mint>(N));
        rep(i, 0, N){
            p3[i][0] = 1;
            rep(j, 1, N){
                p3[i][j] = p3[i][j - 1] * (p2[i] - 1);
            }
        }
        rep(sum, 1, N) rep(fr, 1, N) rep(a, 0, N) if(dp[sum][fr][a].val()){
            rep(k, 1, N + 1 - sum) {
                mint tmp = dp[sum][fr][a] * table.C(N - sum - (a >= K ? 0 : 1), k - (a + 1 == K ? 1 : 0));
                tmp *= p3[fr][k];
                tmp *= p2[k * (k - 1) / 2];
                dp[sum + k][k][a + 1] += tmp;
            }
        }
        rep(i, 0, N + 1) rep(j, 0, N + 1) rep(k, K, N + 1) if (dp[i][j][k].val()) {
            ans[rp] += dp[i][j][k] * p2[(N - i) * (N - i - 1) / 2];
        }
    }
    vector<mint> X(D + 1);
    rep(i, 0, D + 1) X[i] = i + 1;
    auto res = lagrange_interpolation(X, ans);
    /*rep(i, N - 1, M + 1){
        cout << res[i].val() << (i == M ? "\n" : " ");
    }*/
    // for (auto x : res) cout << x.val() << " ";
    // cout << endl;
    cout << res[D - M].val() << "\n";
}