結果
問題 | No.1547 [Cherry 2nd Tune *] 偶然の勝利の確率 |
ユーザー |
![]() |
提出日時 | 2021-06-11 22:50:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 543 ms / 2,000 ms |
コード長 | 1,025 bytes |
コンパイル時間 | 548 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 77,268 KB |
最終ジャッジ日時 | 2024-12-15 01:29:29 |
合計ジャッジ時間 | 9,440 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
mod=998244353 def m(a,b): r=[[0]*len(b[0]) for i in range(len(a))] for i in range(len(a)): for k in range(len(b)): for j in range(len(b[0])): r[i][j]=(r[i][j]+a[i][k]*b[k][j])%mod return r def p(a,n): r=[[0]*len(a) for i in range(len(a))] b=[] for i in range(len(a)): r[i][i]=1 b.append(a[i][:]) l=n while l>0: if l&1: r=m(b,r) b=m(b,b) l>>=1 return r MA,NA,S=map(int,input().split()) MB,NB,T=map(int,input().split()) X,Y=MA*pow(NA,mod-2,mod)%mod,MB*pow(NB,mod-2,mod)%mod K=int(input()) L=S+T+1 A=[[0]*L for i in range(L)] B=[[0]*L for i in range(L)] A[0][0]=1 B[0][0]=1 A[-1][-1]=1 B[-1][-1]=1 for i in range(-T+1,S): x=i y=1 while x<=S: if x==S: A[x+T][i+T]=y break A[x+T][i+T]=(y*(1-X))%mod y=y*X%mod x+=1 x=i y=1 while x>=-T: if x==-T: B[x+T][i+T]=y break B[x+T][i+T]=(y*(1-Y))%mod y=y*Y%mod x-=1 C=[[0]*L for i in range(L)] C[T][-1]=1 Z=m(p(m(B,A),K),C) print(Z[-1][-1],Z[0][-1],sep='\n')