結果

問題 No.3174 勝ち残りじゃんけん
コンテスト
ユーザー t98slider
提出日時 2025-02-23 15:16:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 670 ms / 2,000 ms
コード長 1,444 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,677 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 273,232 KB
最終ジャッジ日時 2025-02-23 17:18:49
合計ジャッジ時間 7,293 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 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] = 1
    for j in range(1, i + 1):
        binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j]
        if binom[i][j] >= 998244353: binom[i][j] -= 998244353

# i人でじゃんけんしたときに引き分けでない手の出し方が何通りあるかの逆数
ndraw_inv = [0] * (N + 1)
pow2 = 2
for i in range(2, N + 1):
    pow2 += pow2
    if pow2 >= 998244353: pow2 -= 998244353
    ndraw_inv[i] = pow(3 * (pow2 - 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
    # i 人において共通である係数を前計算
    coef = (dp[i] * ndraw_inv[i] * 3) % 998244353
    # 減る人数をjとしてループを回す
    for j in range(1, i):
        # i 人から j 人の敗北者を選ぶ
        # (グー、チョキ), (チョキ、パー), (パー、グー)の3通り
        dp[i - j] += binom[i][j] * coef
        dp[i - j] %= 998244353

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

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