結果
問題 | 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])%ModC[i][j]%=Modreturn 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>>=1return E#========================#===入力MA,NA,S=map(int,input().split())MB,NB,T=map(int,input().split())K=int(input())#===定数の設定Mod=998244353rho_A=(MA*pow(NA,Mod-2,Mod))%Modrho_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 0elif x==S+T:U[y][x]=1 if y==S+T else 0else:if y<x:U[y][x]=0else: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 0elif x==S+T:V[y][x]=1 if y==S+T else 0else:if y>x:V[y][x]=0else: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")