結果

問題 No.3174 勝ち残りじゃんけん
コンテスト
ユーザー t98slider
提出日時 2025-02-23 15:02:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,274 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 212 ms
コンパイル使用メモリ 82,812 KB
実行使用メモリ 280,448 KB
最終ジャッジ日時 2025-02-23 17:18:55
合計ジャッジ時間 12,093 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 入力を受け取る
N = int(input())

# 二項係数を前計算
binom = [[0 for j in range(N + 1)] for i in range(N + 1)]
binom[0][0] = 1
for i in range(1, N + 1):
    binom[i][0] = 0
    for j in range(1, i + 1):
        binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j]
        binom[i][j] %= 998244353

# i人でじゃんけんしたときに引き分けでない手の出し方が何通りあるかの逆数
ndraw_inv = [0] * (N + 1)
for i in range(2, N + 1):
    ndraw_inv[i] = pow(3 * (pow(2, i, 998244353) - 2), -1, 998244353)

# 残り1人になるまでに i を経由する確率 dp[i]
dp = [0] * (N + 1)
dp[N] = 1

# 期待値
ans = [0] * N
total = 0
for i in range(N, 1, -1):
    ans[i - 1] = total
    # iを経由する確率と引き分け状態を脱出するまでの期待値の積を取る
    total += dp[i] * pow(3, i, 998244353) * ndraw_inv[i]
    total %= 998244353
    # 減る人数をjとしてループを回す
    for j in range(1, i):
        # i 人から j 人の敗北者を選ぶ
        # (グー、チョキ), (チョキ、パー), (パー、グー)の3通り
        dp[i - j] += dp[i] * binom[i][j] * 3 * ndraw_inv[i]
        dp[i - j] %= 998244353

# 1人になるまでの期待値
ans[0] = total

# 答えを出力
print(*ans)
0