結果

問題 No.3480 Prefix Advantage
コンテスト
ユーザー 👑 potato167
提出日時 2026-03-20 00:09:28
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 188 ms / 2,000 ms
コード長 2,011 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,208 ms
コンパイル使用メモリ 261,208 KB
実行使用メモリ 37,680 KB
最終ジャッジ日時 2026-03-20 20:57:27
合計ジャッジ時間 23,421 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/convolution>
using mint = atcoder::modint998244353;


namespace po167{
template<class T>
struct Binomial{
    std::vector<T> fact_vec, fact_inv_vec;
    void extend(int m = -1){
        int n = fact_vec.size();
        if (m == -1) m = n * 2;
        if (n >= m) return;
        fact_vec.resize(m);
        fact_inv_vec.resize(m);
        for (int i = n; i < m; i++){
            fact_vec[i] = fact_vec[i - 1] * T(i);
        }
        fact_inv_vec[m - 1] = T(1) / fact_vec[m - 1];
        for (int i = m - 1; i > n; i--){
            fact_inv_vec[i - 1] = fact_inv_vec[i] * T(i);
        }
    }
    Binomial(int MAX = 0){
        fact_vec.resize(1, T(1));
        fact_inv_vec.resize(1, T(1));
        extend(MAX + 1);
    }

    T fact(int i){
        if (i < 0) return 0;
        while (int(fact_vec.size()) <= i) extend();
        return fact_vec[i];
    }
    T invfact(int i){
        if (i < 0) return 0;
        while (int(fact_inv_vec.size()) <= i) extend();
        return fact_inv_vec[i];
    }
    T C(int a, int b){
        if (a < b || b < 0) return 0;
        return fact(a) * invfact(b) * invfact(a - b);
    }
    T inv(int a){
        if (a < 0) return inv(-a) * T(-1);
        if (a == 0) return 1;
        return fact(a - 1) * invfact(a);
    }
};
}

vector<mint> solve_fast_2(int N, int P, int Q){
    vector<mint> ans(N + 1);
    po167::Binomial<mint> table;
    vector<mint> tmp(N + 1);
    for (int i = 1; i <= N; i++){
        tmp[i] = table.C(P - 1, i - 1) * table.C(Q - 1, i - 1) * table.inv(i);
    }
    vector<mint> nx(N + 1);
    for (int i = 0; i <= N; i++){
        nx[i] = table.C(P + Q + i, i);
    }
    tmp = atcoder::convolution(tmp, nx);
    tmp.resize(N + 1);
    return tmp;
}


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

	int N, P, Q;
	cin >> N >> P >> Q;
	
	auto ans = solve_fast_2(N, P, Q);
    for (int i = 1; i <= N; i++){
        cout << ans[i].val() << "\n";
    }
}
0