結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
![]() |
提出日時 | 2023-02-05 10:59:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,521 ms / 2,000 ms |
コード長 | 894 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 78,848 KB |
最終ジャッジ日時 | 2024-07-04 01:53:44 |
合計ジャッジ時間 | 59,445 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
import sysreadline = sys.stdin.readlinedef Matprod(A, B, mod):N = len(A)temp = [[0] * N for i in range(N)]for i in range(N):for j in range(N):for k in range(N):temp[i][j] += A[i][k] * B[k][j]temp[i][j] %= modreturn tempdef Matpow(A, M, mod):N = len(A)Mat = [[0] * N for i in range(N)]for i in range(N):Mat[i][i] = 1for i in range(64):if (M >> i) & 1:Mat = Matprod(Mat, A, mod)A = Matprod(A, A, mod)return MatT = int(readline())mod = 10 ** 9 + 7inv = pow(3, mod - 2, mod)M = [[inv, 0, 0, inv, 0, inv],[1, 0, 0, 0, 0, 0],[0, inv, inv, 0, 0, inv],[0, 0, 1, 0, 0, 0],[0, inv, 0, inv, inv, 0],[0, 0, 0, 0, 1, 0],]for _ in range(T):N = int(readline())A = Matpow(M, N, mod)print(A[0][0])