結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
![]() |
提出日時 | 2021-10-09 05:33:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 165 ms / 2,000 ms |
コード長 | 1,042 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 82,920 KB |
実行使用メモリ | 77,804 KB |
最終ジャッジ日時 | 2024-07-23 16:08:44 |
合計ジャッジ時間 | 7,497 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
mod=10**9+7# 行列の計算(numpyを使えないとき,modを使用)def prod(A,B,k,l,m):# A:k*l,B:l*mC=[[None for i in range(m)] for j in range(k)]for i in range(k):for j in range(m):ANS=0for pl in range(l):ANS=(ANS+A[i][pl]*B[pl][j])%modC[i][j]=ANSreturn Cdef plus(A,B,k,l):# a,B:k*lC=[[None for i in range(l)] for j in range(k)]for i in range(k):for j in range(l):C[i][j]=(A[i][j]+B[i][j])%modreturn CINV=pow(3,mod-2,mod)A=[[0]*6 for i in range(6)]A[0][0]=INVA[0][4]=INVA[0][5]=INVA[1][1]=INVA[1][3]=INVA[1][5]=INVA[2][2]=INVA[2][3]=INVA[2][4]=INVA[3][0]=1A[4][1]=1A[5][2]=1POWA=[A]for i in range(60):POWA.append(prod(POWA[-1],POWA[-1],6,6,6)) # ベキを求めてT=int(input())for tests in range(T):n=int(input())X=[[1,0,0,0,0,0]]while n:X=prod(X,POWA[n.bit_length()-1],1,6,6) # n乗の場合n-=1<<(n.bit_length()-1)print(X[0][0])