結果
問題 | No.2443 特殊線形群の標準表現 |
ユーザー |
|
提出日時 | 2023-08-25 22:36:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 995 ms / 3,000 ms |
コード長 | 912 bytes |
コンパイル時間 | 421 ms |
コンパイル使用メモリ | 81,772 KB |
実行使用メモリ | 147,964 KB |
最終ジャッジ日時 | 2024-12-24 09:57:11 |
合計ジャッジ時間 | 9,528 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
def mat_mul(a, b, MOD): """ a: 行列(2次元配列)I*J b: 行列(2次元配列)J*K """ I, J, K = len(a), len(b[0]), len(b) c = [[0] * J for _ in range(I)] for i in range(I): for j in range(J): for k in range(K): c[i][j] += a[i][k] * b[k][j] c[i][j] %= MOD return c N, B, Q = map(int, input().split()) A = [] cumA = [[[1, 0], [0, 1]]] cumA_inv = [[[1, 0], [0, 1]]] for _ in range(N): An = [list(map(int, input().split())) for _ in range(2)] A_inv = [[An[1][1], -An[0][1]], [-An[1][0], An[0][0]]] cumA.append(mat_mul(An, cumA[-1], B)) cumA_inv.append(mat_mul(cumA_inv[-1], A_inv, B)) ans = [] for _ in range(Q): L, R, x, y = map(int, input().split()) C = mat_mul(cumA[R], cumA_inv[L], B) z = (C[0][0]*x+C[0][1]*y) % B w = (C[1][0]*x+C[1][1]*y) % B ans.append((z, w)) for c in ans: print(*c)