結果
問題 |
No.3174 勝ち残りじゃんけん
|
ユーザー |
|
提出日時 | 2025-02-23 01:36:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 153 ms / 2,000 ms |
コード長 | 1,594 bytes |
コンパイル時間 | 3,808 ms |
コンパイル使用メモリ | 255,376 KB |
実行使用メモリ | 101,120 KB |
最終ジャッジ日時 | 2025-02-23 17:18:30 |
合計ジャッジ時間 | 5,656 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using mint = atcoder::modint998244353; int main(){ ios::sync_with_stdio(false); cin.tie(0); // 入力を受け取る int n; cin >> n; // 2項係数を前計算 vector<vector<mint>> binom(n + 1, vector<mint>(n + 1)); binom[0][0] = 1; for(int i = 1; i <= n; i++){ binom[i][0] = 1; for(int j = 1; j <= i; j++){ binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j]; } } // i人でじゃんけんしたときに引き分けでない手の出し方が何通りあるかの逆数 vector<mint> ndraw_inv(n + 1); for(int i = 2; i <= n; i++){ ndraw_inv[i] = (3 * (mint(2).pow(i) - 2)).inv(); } // 残り1人になるまでに i を経由する確率 dp[i] vector<mint> dp(n + 1); dp[n] = 1; // 期待値 vector<mint> ans(n + 1); mint tot = 0; for(int i = n; i >= 2; i--){ ans[i] = tot; // iを経由する確率と引き分け状態を脱出するまでの期待値の積を取る tot += dp[i] * mint(3).pow(i) * ndraw_inv[i]; // 減る人数をjとしてループを回す for(int j = 1; j <= i - 1; j++){ // i 人から j 人の敗者を選ぶ // (グー、チョキ), (チョキ、パー), (パー、グー)の3通り dp[i - j] += dp[i] * binom[i][j] * 3 * ndraw_inv[i]; } } ans[1] = tot; // 答えを出力 for(int i = 1; i <= n; i++){ cout << ans[i].val() << (i == n ? '\n' : ' '); } }