結果
問題 |
No.3174 勝ち残りじゃんけん
|
ユーザー |
![]() |
提出日時 | 2025-06-06 22:44:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 715 ms / 2,000 ms |
コード長 | 1,935 bytes |
コンパイル時間 | 365 ms |
コンパイル使用メモリ | 82,588 KB |
実行使用メモリ | 77,644 KB |
最終ジャッジ日時 | 2025-06-06 22:44:42 |
合計ジャッジ時間 | 6,401 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
class CP: def __init__(self, N): self.fact = [1]*(N+1) self.fact_inv = [1]*(N+1) for i in range(2, N+1): self.fact[i] = self.fact[i-1]*i%MOD self.fact_inv[N] = pow(self.fact[N], -1, MOD) for i in reversed(range(1, N)): self.fact_inv[i] = self.fact_inv[i+1]*(i+1)%MOD def C(self, N, K): if N < 0 or K < 0 or N < K: return 0 return self.fact[N]*self.fact_inv[K]%MOD*self.fact_inv[N-K]%MOD def P(self, N, K): if N < 0 or K < 0 or N < K: return 0 return self.fact[N]*self.fact_inv[N-K]%MOD def H(self, N, K): if N < 0 or K < 0: return 0 if N == K == 0: return 1 return self.C(N+K-1, K) N = int(input()) MOD = 998244353 def inverse(n, d): return n * pow(d, -1, MOD) % MOD cp = CP(N) dp = [0]*(N+1) P = [0]*(N+1) P[N] = 1 imos = [0]*(N+2) imosP = [0]*(N+2) imosP[-2] = 1 imosP[-1] = -1 for i in reversed(range(1, N+1)): if P[i] != 0: dp[i] = inverse(dp[i], P[i]) if i == 1: break # あいこ以外の数 C = 0 for n in range(1, i): C += cp.C(i, n)*3 C %= MOD # 操作回数の期待値 p = inverse(pow(3, i, MOD), C) inv_c = inverse(1, C) for j in range(1, i): # j人が勝つ確率 e = cp.C(i, j)*3%MOD*inv_c%MOD add = (dp[i]+p)%MOD*P[i]%MOD*e%MOD dp[j] += add dp[j] %= MOD imos[j] += add imos[j] %= MOD imos[i] -= add imos[i] %= MOD add = P[i]*e%MOD P[j] += add P[j] %= MOD imosP[j] += add imosP[j] %= MOD imosP[i] -= add imosP[i] %= MOD for i in range(1, N+2): imos[i] += imos[i-1] imos[i] %= MOD imosP[i] += imosP[i-1] imosP[i] %= MOD for i in range(1, N+1): if imosP[i] != 0: imos[i] = inverse(imos[i], imosP[i]) print(*imos[1:-1])