結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
👑 ![]() |
提出日時 | 2021-10-08 23:08:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 419 ms / 2,000 ms |
コード長 | 1,912 bytes |
コンパイル時間 | 330 ms |
コンパイル使用メモリ | 82,036 KB |
実行使用メモリ | 79,316 KB |
最終ジャッジ日時 | 2024-07-23 06:41:27 |
合計ジャッジ時間 | 14,860 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
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+7TT = int(stdin.readline())ANS = []for loop in range(TT):#C,N,M = map(int,stdin.readline().split())C = 3N = int(stdin.readline())M = 3#バス停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)ANS.append(str(ansM[0][0] % mod))#notone = 1 - ansM[0][0]#ans = 1 - pow(notone , M , mod)#print (ans % mod)print ("\n".join(ANS))