結果

問題 No.3174 勝ち残りじゃんけん
コンテスト
ユーザー wgrape
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0