結果

問題 No.3174 勝ち残りじゃんけん
コンテスト
ユーザー t98slider
提出日時 2025-03-02 17:42:25
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 1,876 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,678 ms
コンパイル使用メモリ 259,588 KB
実行使用メモリ 8,608 KB
最終ジャッジ日時 2025-03-02 17:42:31
合計ジャッジ時間 5,797 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;

    // 階乗とその逆数を計算
    vector<mint> fact(N + 1), inv(N + 1);
    fact[0] = 1;
    for(int i = 1; i <= N; i++) fact[i] = mint::raw(i) * fact[i - 1];
    inv[N] = fact[N].inv();
    for(int i = N; i >= 1; i--) inv[i - 1] = mint::raw(i) * inv[i];

    // あいこの通り数を3で割った逆数
    vector<mint> coef(N + 1);
    mint pow2 = 2;
    for(int i = 2; i <= N; i++){
        pow2 += pow2;
        coef[i] = mint(pow2 - 2).inv();
    }

    // ちょうどN - i人になるときの確率とiの階乗とあいこの場合の数の逆数をかけたもの
    vector<mint> dp(N);
    dp[0] = fact[N] * coef[N];

    // オンライン畳み込み
    auto online_convolution = [&](auto self, int l, int r) -> void {
        if(r <= l + 1) return;
        int mid = (l + r) / 2;
        self(self, l, mid);
        vector<mint> tmp_dp(dp.begin() + l, dp.begin() + mid);
        vector<mint> tmp_inv(inv.begin(), inv.begin() + (r - l));
        auto add = convolution(tmp_dp, tmp_inv);
        for(int i = mid; i < r; i++) dp[i] += add[i - l] * coef[N - i];
        self(self, mid, r);
    };
    online_convolution(online_convolution, 0, N);

    vector<mint> ans(N);
    mint tot, pow3 = mint::raw(3).pow(N - 1), div3 = (998244353 + 1) / 3;
    for(int i = 0; i < N; i++){
        ans[N - 1 - i] = tot;
        // 階乗で割り算し, 3**(N - 1 - i)をかけることで
        // ちょうどi人になる確率 と あいこを抜け出すための期待値が求まる
        tot += dp[i] * inv[N - i] * pow3;
        pow3 *= div3;
    }

    for(int i = 0; i < N; i++) cout << ans[i].val() << (i + 1 == N ? '\n' : ' ');
}
0