結果

問題 No.3443 Sum of (Tree Distances)^K 1
コンテスト
ユーザー SnowBeenDiding
提出日時 2026-02-07 00:28:54
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 1,924 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 10,467 ms
コンパイル使用メモリ 425,584 KB
実行使用メモリ 43,516 KB
最終ジャッジ日時 2026-02-07 00:29:20
合計ジャッジ時間 24,505 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 RE * 20
権限があれば一括ダウンロードができます

ソースコード

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;

vector<mint> fact;

mint f(int n, 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;
}

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);

void solve() {
    fact.resize(200010);
    fact[0] = 1;
    rep(i, 1, 200010) fact[i] = fact[i - 1] * i;
    int n, k;
    cin >> n >> k;
    assert(n <= 2000);
    vector<mint> dist_cnt(n + 1);
    rep(i, 1, n) dist_cnt[i] = f(n, i);
    vector<mint> ans(n), distpow(n + 1);
    rep(i, 0, n + 1) distpow[i] = mint(i).pow(k);
    rep(dist, 1, n) {
        mint cnt = dist_cnt[dist];
        mint all = comb(n, dist + 1);
        rep(a, 0, n) {
            mint p = comb(a, dist) / all;
            ans[a] += p * cnt * distpow[dist];
        }
    }
    for (auto x : ans) cout << x.val() << '\n';
}

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