結果
問題 | No.1547 [Cherry 2nd Tune *] 偶然の勝利の確率 |
ユーザー |
👑 ![]() |
提出日時 | 2021-04-10 04:39:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 497 ms / 2,000 ms |
コード長 | 1,733 bytes |
コンパイル時間 | 407 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 77,312 KB |
最終ジャッジ日時 | 2024-12-15 00:45:05 |
合計ジャッジ時間 | 9,167 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#行列の乗算 def mul(A,B): size=len(A) C=[[0]*(size+1) for _ in range(size)] for i in range(size): for j in range(size): for k in range(size): C[i][j]+=(A[i][k]*B[k][j])%Mod C[i][j]%=Mod return C #行列の累乗 def power(A,k): size=len(A) E=[[1 if y==x else 0 for y in range(size)] for x in range(size)] while k: if k&1: E=mul(E,A) A=mul(A,A) k>>=1 return E #======================== #===入力 MA,NA,S=map(int,input().split()) MB,NB,T=map(int,input().split()) K=int(input()) #===定数の設定 Mod=998244353 rho_A=(MA*pow(NA,Mod-2,Mod))%Mod rho_B=(MB*pow(NB,Mod-2,Mod))%Mod #===Aについての行列 U=[[0]*(S+T+1) for _ in range(S+T+1)] for y in range(S+T+1): for x in range(S+T+1): if x==0: U[y][x]=1 if y==0 else 0 elif x==S+T: U[y][x]=1 if y==S+T else 0 else: if y<x: U[y][x]=0 else: if y==S+T: U[y][x]=pow(rho_A,y-x,Mod) else: U[y][x]=(pow(rho_A,y-x,Mod)*(1-rho_A))%Mod #===Bについての行列 V=[[0]*(S+T+1) for _ in range(S+T+1)] for y in range(S+T+1): for x in range(S+T+1): if x==0: V[y][x]=1 if y==0 else 0 elif x==S+T: V[y][x]=1 if y==S+T else 0 else: if y>x: V[y][x]=0 else: if y==0: V[y][x]=pow(rho_B,x-y,Mod) else: V[y][x]=(pow(rho_B,x-y,Mod)*(1-rho_B))%Mod #===行列の計算 M=mul(V,U) E=power(M,K) #===結果の出力 print(E[S+T][T],E[0][T],sep="\n")