結果

問題 No.3443 Sum of (Tree Distances)^K 1
コンテスト
ユーザー SnowBeenDiding
提出日時 2026-02-07 00:50:52
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 257 ms / 2,000 ms
コード長 2,287 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,053 ms
コンパイル使用メモリ 431,652 KB
実行使用メモリ 52,744 KB
最終ジャッジ日時 2026-02-07 00:51:14
合計ジャッジ時間 21,013 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#include <atcoder/all>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
using namespace atcoder;
using namespace std;

typedef long long ll;

using mint = modint998244353;

struct Comb {
    vector<mint> fact, ifact;
    int MAX_COM;
    Comb() {}
    Comb(int n, int mod) {
        MAX_COM = n;
        init(mod, MAX_COM);
    }
    void init(long long MOD, long long MAX_COM) {
        int n = MAX_COM;
        assert(n < MOD);
        fact = vector<mint>(n + 1);
        ifact = vector<mint>(n + 1);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }
    mint operator()(long long n, long long k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
};
Comb comb(5000010, 998244353);

vector<mint> binomial_transform(vector<mint> f) {
    // ans[i] = Σ (j=0 to i) f[j] * comb(i, j)
    int n = f.size();
    vector<mint> fact(n), invfact(n);
    fact[0] = 1;
    for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i;
    invfact[n - 1] = fact[n - 1].inv();
    for (int i = n - 1; i > 0; i--) invfact[i - 1] = invfact[i] * i;
    vector<mint> A(n), B(n);
    for (int i = 0; i < n; i++) {
        A[i] = f[i] * invfact[i];
        B[i] = invfact[i];
    }
    auto C = convolution(A, B);
    vector<mint> ans(n);
    for (int i = 0; i < n; i++) {
        ans[i] = C[i] * fact[i];
    }
    return ans;
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<mint> fact(n);
    fact[0] = 1;
    rep(i, 1, n) fact[i] = fact[i - 1] * i;
    auto count_len = [&](int len) {
        len++;
        mint ret = pow_mod(n, n - len, 998244353);
        ret *= len;
        ret *= fact[n - 1];
        ret /= fact[n - len];
        ret /= 2;
        return ret;
    };
    vector<mint> f(n);
    rep(i, 0, n) f[i] = count_len(i) * mint(i).pow(k) / comb(n, i + 1);
    auto ans = binomial_transform(f);
    for (auto x : ans) cout << x.val() << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    solve();
}
0