結果

問題 No.3445 Sum of (Tree Distances)^K 2
コンテスト
ユーザー noya2
提出日時 2026-02-05 17:34:52
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 1,607 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,224 ms
コンパイル使用メモリ 345,012 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2026-02-06 20:58:43
合計ジャッジ時間 10,000 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// O(N^2) time, 60sec with N=200000
#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;

vector<mint> enumerate_powers(int n, int k) {
    vector<mint> powers(n + 1);
    vector<int> primes;
    vector<bool> is_prime(n + 1, true);
    powers[1] = 1;
    for (int i = 2; i <= n; i++){
        if (is_prime[i]){
            primes.emplace_back(i);
            powers[i] = mint(i).pow(k);
        }
        for (int p : primes){
            if (i * p > n) break;
            is_prime[i * p] = false;
            powers[i * p] = powers[i] * powers[p];
            if (i % p == 0) break;
        }
    }
    return powers;
}

int main(){
    int n, k; cin >> n >> k;
    vector<mint> inv(n);
    inv[0] = 1;
    for (int i = 1; i < n; i++){
        inv[i] = inv[i-1] * i;
    }
    mint fact = inv[n-1];
    mint ifact = fact.inv();
    for (int i = n-1; i >= 1; i--){
        inv[i] = ifact * inv[i-1];
        ifact *= i;
    }
    vector<mint> ps = enumerate_powers(n, k);
    vector<mint> g(n);
    auto proc = [&](int i){
        i--;
        mint c = inv[i] * 2;
        for (int j = n-1; j >= 1; j--){
            g[j] = g[j] * c + g[j-1];
        }
        g[0] *= c;
        int lim = n - i;
        for (int j = 0; j < lim; j++){
            g[j + i] += ps[j + 1];
        }
    };
    vector<uint32_t> say(n);
    for (int a = 2; a <= n; a++){
        proc(a-1);
        mint ans = g[a-2];
        ans *= fact;
        ans *= inv[a-1];
        say[a-1] = ans.val();
    }
    for (int i = 0; i < n; i++){
        cout << say[i] << '\n';
    }
}
0