結果
問題 |
No.3174 勝ち残りじゃんけん
|
ユーザー |
![]() |
提出日時 | 2025-08-08 11:57:38 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,462 bytes |
コンパイル時間 | 452 ms |
コンパイル使用メモリ | 82,360 KB |
実行使用メモリ | 77,196 KB |
最終ジャッジ日時 | 2025-08-08 11:57:43 |
合計ジャッジ時間 | 4,469 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 1 TLE * 1 -- * 15 |
ソースコード
MOD = 998244353 def modinv(a): # 逆元 (フェルマーの小定理) return pow(a, MOD - 2, MOD) def solve(): import sys sys.setrecursionlimit(10000) N = int(sys.stdin.readline()) # dp[i]: 勝ち残り人数が i 人になるまでの期待回数 (mod 998244353) dp = [0] * (N + 1) # 確率計算のための組み合わせ数 (nCr) from math import comb # 事前計算: P(i -> j) の確率 (mod 998244353) prob = [[0] * (N + 1) for _ in range(N + 1)] for i in range(2, N + 1): total_cases = pow(3, i, MOD) # 3^i の場合の数 (mod) inv_total = modinv(total_cases) for j in range(1, i): # 勝者が j 人になるケースを数える # 勝者グー j 人、残りチョキ (j != 0, 残り != 0) cnt = 0 cnt += comb(i, j) * pow(2, i - j) cnt += comb(i, j) * pow(2, i - j) cnt += comb(i, j) * pow(2, i - j) cnt %= MOD prob[i][j] = (cnt * inv_total) % MOD # DP 計算 for i in range(2, N + 1): s = 1 # 自分の1回の操作 for j in range(1, i): s = (s + prob[i][j] * dp[j]) % MOD # 引き分け確率 p_draw = (1 - sum(prob[i][1:i]) % MOD + MOD) % MOD dp[i] = (s * modinv((1 - p_draw + MOD) % MOD)) % MOD print(" ".join(str(dp[i]) for i in range(1, N + 1))) if __name__ == "__main__": solve()