結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
|
提出日時 | 2022-04-26 11:59:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 548 ms / 2,000 ms |
コード長 | 924 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 77,556 KB |
最終ジャッジ日時 | 2024-06-28 07:27:51 |
合計ジャッジ時間 | 18,411 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
T = int(input())P = 10 ** 9 + 7n = 6def seki(x,y):n = 6l = [[0] * n for _ in range(n)]for i in range(n):for j in range(n):for k in range(n):l[i][j] += x[i][k] * y[k][j] % Pl[i][j] %= Preturn linv = pow(3,P-2,P)R = [[0] * n for _ in range(n)]e = [[0] * n for _ in range(n)]for i in range(n):e[i][i] = 1for i in range(3):R[i][i+3] = 1R[i+3][i+3] = invfor i in range(3):for j in range(3):if i == j:continueR[i + 3][j] = invfor _ in range(T):N = int(input())ee = [[0] * n for _ in range(n)]RR = [[0] * n for _ in range(n)]for i in range(n):for j in range(n):ee[i][j] = e[i][j]RR[i][j] = R[i][j]while N:if N & 1:ee = seki(ee,RR)RR = seki(RR,RR)N >>= 1ans = ee[0][0] + ee[0][3] * invprint(ans % P)