結果
問題 |
No.2443 特殊線形群の標準表現
|
ユーザー |
![]() |
提出日時 | 2023-08-27 15:24:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 793 ms / 3,000 ms |
コード長 | 979 bytes |
コンパイル時間 | 355 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 183,808 KB |
最終ジャッジ日時 | 2024-12-27 16:13:02 |
合計ジャッジ時間 | 9,394 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import sys input = sys.stdin.readline def prod(A, B, mod): C = [[0] * 2 for i in range(2)] for i in range(2): for j in range(2): for k in range(2): C[i][j] += A[i][k] * B[k][j] C[i][j] %= mod return C def inv(M): a, b = M[0] c, d = M[1] return [[d, -b], [-c, a]] N, B, Q = map(int, input().split()) A = [[] for i in range(N)] R = [[] for i in range(N)] for i in range(N): for j in range(2): A[i].append(list(map(int, input().split()))) R[i] = inv(A[i]) Ac = [[[1, 0], [0, 1]]] * (N + 1) Rc = [[[1, 0], [0, 1]]] * (N + 1) for i in range(N): Ac[i + 1] = prod(A[i], Ac[i], B) Rc[i + 1] = prod(Rc[i], R[i], B) for _ in range(Q): L, R, x, y = map(int, input().split()) x1 = Rc[L][0][0] * x + Rc[L][0][1] * y y1 = Rc[L][1][0] * x + Rc[L][1][1] * y x2 = Ac[R][0][0] * x1 + Ac[R][0][1] * y1 y2 = Ac[R][1][0] * x1 + Ac[R][1][1] * y1 print(x2%B, y2%B)