#1152902 (C++17) No.3480 Prefix Advantage

• 問題: No.3480 Prefix Advantage
• ユーザー: 👑 potato167
• 提出日時: 2026-03-20 00:11:20
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 316 ms / 2,000 ms
• コード長: 3,140 bytes
• コンパイル時間: 1,446 ms
• コンパイル使用メモリ: 223,340 KB
• 実行使用メモリ: 63,300 KB
• 最終ジャッジ日時: 2026-03-20 20:57:27
• 合計ジャッジ時間: 25,829 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 60

ソースコード

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

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

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

void ntt(vector<long long>& a, bool invert) {
    int n = (int)a.size();

    static vector<int> rev;
    static vector<long long> roots{0, 1};

    if ((int)rev.size() != n) {
        int k = __builtin_ctz(n);
        rev.assign(n, 0);
        for (int i = 0; i < n; i++) {
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
        }
    }

    if ((int)roots.size() < n) {
        int k = __builtin_ctz((int)roots.size());
        roots.resize(n);
        while ((1 << k) < n) {
            long long e = modpow(G, (MOD - 1) >> (k + 1));
            for (int i = 1 << (k - 1); i < (1 << k); i++) {
                roots[2 * i] = roots[i];
                roots[2 * i + 1] = roots[i] * e % MOD;
            }
            k++;
        }
    }

    for (int i = 0; i < n; i++) {
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    }

    for (int len = 1; len < n; len <<= 1) {
        for (int i = 0; i < n; i += 2 * len) {
            for (int j = 0; j < len; j++) {
                long long u = a[i + j];
                long long v = a[i + j + len] * roots[len + j] % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len] = (u - v + MOD) % MOD;
            }
        }
    }

    if (invert) {
        reverse(a.begin() + 1, a.end());
        long long inv_n = modpow(n, MOD - 2);
        for (auto& x : a) x = x * inv_n % MOD;
    }
}

vector<long long> convolution(vector<long long> a, vector<long long> b) {
    int need = (int)a.size() + (int)b.size() - 1;
    int n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

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

    int P, Q, N;
    cin >> N >> P >> Q;

    int m = min(P, Q);
    int M = max(P, Q);
    int D = P + Q;

    int LIM = N + D + 5;
    vector<long long> fact(LIM), ifact(LIM);
    fact[0] = 1;
    for (int i = 1; i < LIM; i++) fact[i] = fact[i - 1] * i % MOD;
    ifact[LIM - 1] = modpow(fact[LIM - 1], MOD - 2);
    for (int i = LIM - 1; i >= 1; i--) ifact[i - 1] = ifact[i] * i % MOD;

    auto C = [&](int n, int r) -> long long {
        if (r < 0 || r > n) return 0;
        return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
    };

    long long inv_m = modpow(m, MOD - 2);

    // A[k] = (1/m) * C(m,k) * C(M-1,k-1), 1<=k<=m
    vector<long long> A(m + 1, 0);
    for (int k = 1; k <= m; k++) {
        A[k] = inv_m * C(m, k) % MOD * C(M - 1, k - 1) % MOD;
    }

    // B[t] = C(t + D, D), 0<=t<=N-1
    vector<long long> B(N, 0);
    for (int t = 0; t < N; t++) {
        B[t] = C(t + D, D);
    }

    auto conv = convolution(A, B);

    for (int n = 1; n <= N; n++) {
        cout << conv[n] % MOD << '\n';
    }

    return 0;
}