結果

問題 No.1145 Sums of Powers
ユーザー vjudge1
提出日時 2025-10-01 18:06:45
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 861 ms / 2,000 ms
コード長 3,305 bytes
コンパイル時間 2,573 ms
コンパイル使用メモリ 176,592 KB
実行使用メモリ 25,920 KB
最終ジャッジ日時 2025-10-01 18:06:52
合計ジャッジ時間 5,923 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int MOD = 998244353;
const int G = 3;

long long pow_mod(long long base, long long exp) {
    long long result = 1;
    while (exp) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

void ntt(vector<long long> &a, int inv) {
    int n = a.size();
    int bit = 0;
    while ((1 << bit) < n) bit++;
    vector<int> rev(n);
    for (int i = 0; i < n; i++) {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    }
    for (int mid = 1; mid < n; mid <<= 1) {
        long long wn = pow_mod(G, (MOD - 1) / (mid * 2));
        if (inv == -1) wn = pow_mod(wn, MOD - 2);
        for (int i = 0; i < n; i += mid * 2) {
            long long w = 1;
            for (int j = 0; j < mid; j++, w = w * wn % MOD) {
                long long x = a[i + j], y = w * a[i + j + mid] % MOD;
                a[i + j] = (x + y) % MOD;
                a[i + j + mid] = (x - y + MOD) % MOD;
            }
        }
    }
    if (inv == -1) {
        long long inv_n = pow_mod(n, MOD - 2);
        for (int i = 0; i < n; i++) a[i] = a[i] * inv_n % MOD;
    }
}

vector<long long> poly_mult(vector<long long> a, vector<long long> b, int maxn = -1) {
    int n = 1;
    int len = a.size() + b.size() - 1;
    while (n < len) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, 1);
    ntt(b, 1);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, -1);
    if (maxn != -1 && a.size() > maxn) a.resize(maxn);
    return a;
}

vector<long long> poly_inv(vector<long long> a, int n) {
    if (n == 1) {
        return {pow_mod(a[0], MOD - 2)};
    }
    vector<long long> b = poly_inv(a, (n + 1) >> 1);
    int len = 1;
    while (len < n * 2) len <<= 1;
    vector<long long> a_cpy = a;
    a_cpy.resize(n);
    a_cpy.resize(len);
    b.resize(len);
    ntt(a_cpy, 1);
    ntt(b, 1);
    for (int i = 0; i < len; i++) {
        b[i] = (2 - a_cpy[i] * b[i] % MOD + MOD) % MOD * b[i] % MOD;
    }
    ntt(b, -1);
    b.resize(n);
    return b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, M;
    cin >> N >> M;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    if (N == 0) {
        for (int i = 0; i < M; i++) {
            cout << 0 << " ";
        }
        cout << endl;
        return 0;
    }
    
    queue<vector<long long>> q;
    for (int i = 0; i < N; i++) {
        vector<long long> poly(2);
        poly[0] = 1;
        poly[1] = (-A[i] % MOD + MOD) % MOD;
        q.push(poly);
    }
    
    while (q.size() > 1) {
        auto a = q.front(); q.pop();
        auto b = q.front(); q.pop();
        auto c = poly_mult(a, b, M + 1);
        q.push(c);
    }
    vector<long long> Q = q.front();
    Q.resize(M + 1);
    
    vector<long long> R(M + 1, 0);
    int min_nm = min(N, M);
    for (int k = 1; k <= min_nm; k++) {
        R[k] = (-k * Q[k]) % MOD;
        if (R[k] < 0) R[k] += MOD;
    }
    
    vector<long long> InvQ = poly_inv(Q, M + 1);
    vector<long long> T = poly_mult(R, InvQ, M + 1);
    
    for (int k = 1; k <= M; k++) {
        cout << T[k] << " ";
    }
    cout << endl;
    
    return 0;
}
0