結果

問題 No.3445 Sum of (Tree Distances)^K 2
コンテスト
ユーザー 👑 potato167
提出日時 2025-12-26 02:11:59
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,161 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,132 ms
コンパイル使用メモリ 217,684 KB
実行使用メモリ 20,516 KB
最終ジャッジ日時 2026-02-06 20:50:27
合計ジャッジ時間 9,128 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

static const long long MOD = 998244353;

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

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

    int N;
    long long K;
    cin >> N >> K;

    // precompute i^K
    vector<long long> pw(N + 1, 0);
    for (int i = 1; i <= N; i++) pw[i] = modpow(i, K);

    // factorials
    vector<long long> fac(N + 1, 1), ifac(N + 1, 1);
    for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[N] = modpow(fac[N], MOD - 2);
    for (int i = N; i >= 1; i--) ifac[i - 1] = ifac[i] * i % MOD;

    // DP arrays: P holds P_m(c) for current m, c=1..len
    // Start with m=1: P_1(c)=c^K, and the needed max c is N-1.
    int len = N - 1;
    vector<long long> P(N + 2, 0), Q(N + 2, 0);

    for (int c = 1; c <= len; c++) P[c] = pw[c];

    // F[a] = P_{a-1}(1)
    vector<long long> F(N + 1, 0);
    F[1] = 0;

    // m is current size (number of vertices in the recursive tree)
    // We will fill F[m+1] = P_m(1) for m=1..N-1.
    for (int m = 1; m <= N - 1; m++) {
        F[m + 1] = P[1];  // P_m(1) (valid for m <= N-1)

        if (m == N - 1) break;

        // compute P_{m+1}(c) for c=1..(len-1)
        // recurrence: P_{m+1}(c)= m*P_m(c) + 2*P_m(c+1) + m!*c^K
        // here m! = fac[m]
        fill(Q.begin(), Q.end(), 0);
        for (int c = 1; c <= len - 1; c++) {
            long long val = 0;
            val += (long long)m * P[c] % MOD;
            val += 2LL * P[c + 1] % MOD;
            val += fac[m] * pw[c] % MOD;
            Q[c] = val % MOD;
        }

        P.swap(Q);
        len--;
    }

    // Answer for each a:
    // Ans[a] = (N-1)!/(a-1)! * F[a]  (mod MOD)
    for (int a = 1; a <= N; a++) {
        long long ans = 0;
        if (a == 1) {
            ans = 0;
        } else {
            long long coef = fac[N - 1] * ifac[a - 1] % MOD;
            ans = coef * (F[a] % MOD) % MOD;
        }
        cout << ans << "\n";
    }
    return 0;
}
0