結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
![]() |
提出日時 | 2023-02-05 11:04:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 985 ms / 2,000 ms |
コード長 | 901 bytes |
コンパイル時間 | 232 ms |
コンパイル使用メモリ | 82,264 KB |
実行使用メモリ | 78,084 KB |
最終ジャッジ日時 | 2024-07-04 01:56:12 |
合計ジャッジ時間 | 37,367 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
import sys readline = sys.stdin.readline def 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] %= mod return temp def Matpow(A, M, mod): N = len(A) Mat = [[0] * N for i in range(N)] for i in range(N): Mat[i][i] = 1 for i in range(32): if (M >> i) & 1: Mat = Matprod(Mat, A, mod) A = Matprod(A, A, mod) return Mat T = int(readline()) mod = 10 ** 9 + 7 inv = pow(3, mod - 2, mod) M = [[1, 0, 0, 1, 0, 1], [3, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 1], [0, 0, 3, 0, 0, 0], [0, 1, 0, 1, 1, 0], [0, 0, 0, 0, 3, 0],] for _ in range(T): N = int(readline()) A = Matpow(M, N, mod) print(A[0][0] * pow(inv, N, mod) % mod)