結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
|
提出日時 | 2022-01-29 17:46:59 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 625 ms / 2,000 ms |
コード長 | 660 bytes |
コンパイル時間 | 226 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 31,448 KB |
最終ジャッジ日時 | 2025-01-02 11:07:10 |
合計ジャッジ時間 | 24,447 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
import numpy as npT = int(input())MOD = 10 ** 9 + 7M = np.array([[1, 0, 0, 0, 1, 1],[0, 1, 0, 1, 0, 1],[0, 0, 1, 1, 1, 0],[3, 0, 0, 0, 0, 0],[0, 3, 0, 0, 0, 0],[0, 0, 3, 0, 0, 0],])doubling = [M]for i in range(40):doubling.append(doubling[-1] @ doubling[-1])doubling[-1] = np.mod(doubling[-1], MOD)fraction = pow(3, MOD - 2, MOD)for _ in range(T):N = int(input())V = np.array([1, 0, 0, 3, 0, 0])for i in range(40)[::-1]:if N >> i & 1:V = doubling[i] @ VV = np.mod(V, MOD)print(V[3] * pow(fraction, N + 1, MOD) % MOD)