結果
問題 | No.1706 Many Bus Stops (hard) |
ユーザー |
👑 ![]() |
提出日時 | 2021-10-08 23:04:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 1,662 bytes |
コンパイル時間 | 326 ms |
コンパイル使用メモリ | 82,504 KB |
実行使用メモリ | 63,028 KB |
最終ジャッジ日時 | 2024-07-23 06:30:19 |
合計ジャッジ時間 | 3,543 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
"""1704&1706行列べき乗はそれはそう。バス停11 -> ?? -> 1? -> ?バス停?の5通りしか存在しないと考えてよい。あとは、1台がいる確率をそれぞれ求めて一台もいない確率を計算すればおk"""from sys import stdinimport sysmod = 10**9+7def inverse(x,mod):return pow(x,mod-2,mod)def matrix_mul(A,B,mod):ans = [ [0] * len(B[0]) for i in range(len(A)) ]for ai in range(len(A)):for bj in range(len(B[0])):now = 0for same in range(len(A[0])):now += A[ai][same] * B[same][bj]if mod > 0:ans[ai][bj] = now % modelse:ans[ai][bj] = nowreturn ans#行列Aのx乗(当然正方行列じゃないとだめ)def matrix_pow(A,x,mod):B = [[A[i][j] for j in range(len(A[0]))] for i in range(len(A))]ans = [[0] * len(A[0]) for i in range(len(A))]for i in range(len(A)):ans[i][i] = 1while x > 0:if x % 2 == 1:ans = matrix_mul(ans,B,mod)B = matrix_mul(B,B,mod)x//=2return ansmod = 10**9+7C,N,M = map(int,stdin.readline().split())#バス停1#1 -> ?#? -> 1#? -> ?#バス停?CINV = inverse(C,mod)OA = [[1,0,0,0,0]]A = [ [CINV , (1-CINV) % mod , 0 , 0 , 0 ],[0 , 0 , 0 , 0 , 1 ],[1 , 0 , 0 , 0 , 0],[0 , 0 , 0 , 0 , 1],[0 , 0 , CINV , (1-2*CINV) % mod , CINV]]ansM = matrix_mul(OA,matrix_pow(A,N,mod),mod)notone = 1 - ansM[0][0]ans = 1 - pow(notone , M , mod)print (ans % mod)