結果
問題 |
No.3174 勝ち残りじゃんけん
|
ユーザー |
![]() |
提出日時 | 2025-06-06 22:42:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,695 ms / 2,000 ms |
コード長 | 1,406 bytes |
コンパイル時間 | 384 ms |
コンパイル使用メモリ | 82,572 KB |
実行使用メモリ | 84,608 KB |
最終ジャッジ日時 | 2025-06-06 22:42:16 |
合計ジャッジ時間 | 11,680 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
mod=998244353 class Comb: def __init__(self, lim:int, mod:int = mod): """ mod : prime """ self.fac = [1]*(lim+1) self.finv = [1]*(lim+1) self.mod = mod for i in range(2,lim+1): self.fac[i] = self.fac[i-1]*i%self.mod self.finv[lim] = pow(self.fac[lim],-1,mod) for i in range(lim,2,-1): self.finv[i-1] = self.finv[i]*i%self.mod def C(self, a, b): assert b >= 0, "The second argument is negative." if a < b: return 0 if a < 0: return 0 return self.fac[a]*self.finv[b]%self.mod*self.finv[a-b]%self.mod def P(self, a, b): assert b >= 0, "The second argument is negative." if a < b: return 0 if a < 0: return 0 return self.fac[a]*self.finv[a-b]%self.mod def H(self, a, b): return self.C(a+b-1,b) def F(self, a): return self.fac[a] def Fi(self, a): return self.finv[a] comb = Comb(10000, mod) N=int(input()) dp = [0]*(N+1) dp[N] = 1 for i in range(N,1,-1): t = pow(pow(2,i,mod)-2, -1, mod) for j in range(1,i): dp[j] += dp[i] * comb.C(i,j) * t dp[j] %= mod ans = 0 a = [0] for i in range(N,1,-1): #ans += dp[i] ans %= mod p = (pow(3,i,mod)-(pow(2,i,mod)-2)*3) * pow(pow(3,i,mod), -1, mod)%mod ans += dp[i] * pow(1-p,-1,mod) ans %= mod a.append(ans) print(*a[::-1])