結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
|
提出日時 | 2021-10-08 23:04:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,850 ms / 2,000 ms |
コード長 | 925 bytes |
コンパイル時間 | 191 ms |
コンパイル使用メモリ | 82,436 KB |
実行使用メモリ | 90,240 KB |
最終ジャッジ日時 | 2024-07-23 06:29:36 |
合計ジャッジ時間 | 45,762 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
MOD = 10 ** 9 + 7i3 = pow(3, -1, MOD)"""pypy用行列累乗ライブラリは https://github.com/fujihiraryo/alogorithm-python/blob/master/integer/matrix.py から拝借しています。"""def product(a, b, p=MOD):n = len(a)c = [[0] * n for i in range(n)]for i in range(n):for j in range(n):c[i][j] = sum([a[i][k] * b[k][j] for k in range(n)]) % preturn cdef matpow(a, k, p=10 ** 9 + 7):if k == 1:return aif k % 2 == 0:b = matpow(a, k // 2)return product(b, b, p=p)return product(a, matpow(a, k - 1), p=p)def solve(N):x = [1, 0, 0, 0, 0, 0]A = [[i3, 0, 0, 0, i3, i3],[0, i3, 0, i3, 0, i3],[0, 0, i3, i3, i3, 0],[1, 0, 0, 0, 0, 0],[0, 1, 0, 0, 0, 0],[0, 0, 1, 0, 0, 0]]return matpow(A, N)[0][0]T = int(input())for _ in range(T):print(solve(int(input())))