結果

問題 No.3174 勝ち残りじゃんけん
ユーザー t98slider
提出日時 2025-02-25 02:29:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 463 ms / 2,000 ms
コード長 1,604 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 77,008 KB
最終ジャッジ日時 2025-02-25 02:29:26
合計ジャッジ時間 4,496 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

# 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(pow2 - 2, -1, 998244353)

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

# 期待値
ans = [0] * N
total = 0
pow3 = pow(3, N - 1, 998244353)
div3 = (1 + 998244353) // 3
for i in range(N, 1, -1):
    ans[i - 1] = total

    # i 人において共通である係数を前計算
    coef = dp[i] * ndraw_inv[i] % 998244353
    # iを経由する確率と引き分け状態を脱出するまでの期待値の積を取る
    total += coef * pow3 % 998244353
    if total >= 998244353 : total -= 998244353

    pow3 *= div3
    pow3 %= 998244353

    # 減る人数をjとしてループを回す
    for j in range(1, i):
        # i 人から j 人の敗北者を選ぶ
        # (グー、チョキ), (チョキ、パー), (パー、グー)の3通り
        dp[i - j] += binom[j] * coef % 998244353
        if dp[i - j] >= 998244353 : dp[i - j] -= 998244353
        binom[j] -= binom[j - 1]
        if binom[j] < 0: binom[j] += 998244353

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

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