結果
問題 | No.2443 特殊線形群の標準表現 |
ユーザー | rlangevin |
提出日時 | 2023-08-27 15:24:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,037 ms / 3,000 ms |
コード長 | 979 bytes |
コンパイル時間 | 1,878 ms |
コンパイル使用メモリ | 86,764 KB |
実行使用メモリ | 184,804 KB |
最終ジャッジ日時 | 2023-08-27 15:24:24 |
合計ジャッジ時間 | 11,485 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
71,064 KB |
testcase_01 | AC | 73 ms
70,916 KB |
testcase_02 | AC | 74 ms
71,124 KB |
testcase_03 | AC | 76 ms
71,336 KB |
testcase_04 | AC | 74 ms
71,276 KB |
testcase_05 | AC | 74 ms
71,168 KB |
testcase_06 | AC | 75 ms
71,064 KB |
testcase_07 | AC | 75 ms
70,896 KB |
testcase_08 | AC | 74 ms
71,036 KB |
testcase_09 | AC | 76 ms
71,440 KB |
testcase_10 | AC | 75 ms
71,032 KB |
testcase_11 | AC | 81 ms
71,056 KB |
testcase_12 | AC | 88 ms
75,560 KB |
testcase_13 | AC | 158 ms
78,272 KB |
testcase_14 | AC | 225 ms
88,644 KB |
testcase_15 | AC | 945 ms
184,188 KB |
testcase_16 | AC | 1,037 ms
184,636 KB |
testcase_17 | AC | 880 ms
184,804 KB |
testcase_18 | AC | 917 ms
184,420 KB |
testcase_19 | AC | 917 ms
184,580 KB |
testcase_20 | AC | 720 ms
184,416 KB |
ソースコード
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)