結果

問題 No.2135 C5
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:21:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 613 ms / 2,000 ms
コード長 3,438 bytes
コンパイル時間 773 ms
コンパイル使用メモリ 77,652 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-14 13:23:42
合計ジャッジ時間 10,031 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

long long MOD = 998244353;

vector<long long> fact;
vector<long long> invFact;
long long INV2;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, MOD - 2);
}

void precompute_factorials(int n) {
    fact.resize(n + 1);
    invFact.resize(n + 1);
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
        invFact[i] = modInverse(fact[i]);
    }
    INV2 = modInverse(2);
}

long long nCr_mod_p(int n, int r) {
    if (r < 0 || r > n) return 0;
    return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    precompute_factorials(N);

    long long M_bar = (long long)N * (N - 1) / 2 - M;

    if (M_bar < 0 || M_bar > N) {
        cout << 0 << endl;
        return 0;
    }
    
    // dp[i][j] = number of ways to form a graph on i vertices with j edges,
    // where graph is a collection of disjoint paths and cycles C_k (k>=5)
    vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, 0));
    dp[0][0] = 1;

    // f[k][l] = ways to form one component (path or Ck, k>=5) on k specific vertices with l edges
    vector<vector<long long>> f(N + 1, vector<long long>(N + 1, 0));

    // P1
    f[1][0] = 1; 
    // Paths P_k, k >= 2
    for (int k = 2; k <= N; ++k) {
        if (k - 1 <= N) { // Edges l = k-1
             f[k][k-1] = (fact[k] * INV2) % MOD;
        }
    }
    // Cycles C_k, k >= 5
    for (int k = 5; k <= N; ++k) {
        if (k <= N) { // Edges l = k
            f[k][k] = (fact[k-1] * INV2) % MOD;
        }
    }
    // Special cases for small N where C_k, k>=5 is impossible
    // For N=3, C3 would be fact[2]*INV2 = 1. f[3][3] should be 0.
    // For N=4, C4 would be fact[3]*INV2 = 3. f[4][4] should be 0.
    if (N >=3 && 3 <= N) f[3][3] = 0; // No C3
    if (N >=4 && 4 <= N) f[4][4] = 0; // No C4
    

    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= i; ++j) { // Max edges in such a graph on i vertices is i
            for (int k = 1; k <= i; ++k) { // Size of component involving vertex i
                // Path component
                if (k - 1 <= j) { // l = k-1 edges
                    long long ways_comp = f[k][k-1];
                    if (ways_comp > 0) {
                        long long term = (nCr_mod_p(i - 1, k - 1) * ways_comp) % MOD;
                        term = (term * dp[i - k][j - (k - 1)]) % MOD;
                        dp[i][j] = (dp[i][j] + term) % MOD;
                    }
                }

                // Cycle component (C_k, k>=5)
                if (k <= j) { // l = k edges
                    long long ways_comp = f[k][k]; // This is already 0 if k<5
                     if (ways_comp > 0) {
                        long long term = (nCr_mod_p(i - 1, k - 1) * ways_comp) % MOD;
                        term = (term * dp[i - k][j - k]) % MOD;
                        dp[i][j] = (dp[i][j] + term) % MOD;
                    }
                }
            }
        }
    }

    cout << dp[N][M_bar] << endl;

    return 0;
}
0