結果
問題 |
No.2443 特殊線形群の標準表現
|
ユーザー |
![]() |
提出日時 | 2025-04-09 20:57:37 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,742 bytes |
コンパイル時間 | 340 ms |
コンパイル使用メモリ | 82,036 KB |
実行使用メモリ | 155,156 KB |
最終ジャッジ日時 | 2025-04-09 20:59:36 |
合計ジャッジ時間 | 5,202 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 WA * 14 |
ソースコード
def main(): import sys input = sys.stdin.read data = input().split() ptr = 0 N = int(data[ptr]) ptr += 1 B = int(data[ptr]) ptr += 1 Q = int(data[ptr]) ptr += 1 # Identity matrix def identity(): return [[1 % B, 0 % B], [0 % B, 1 % B]] # Multiply two matrices mod B def multiply(m1, m2, mod): a = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % mod b = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % mod c = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % mod d = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % mod return [[a, b], [c, d]] # Compute the inverse matrix mod B def inverse_matrix(mat, mod): a, b = mat[0][0], mat[0][1] c, d = mat[1][0], mat[1][1] inv_a = d % mod inv_b = (-b) % mod inv_c = (-c) % mod inv_d = a % mod return [[inv_a, inv_b], [inv_c, inv_d]] # Read the matrices and precompute prefix products prefix = [identity()] for _ in range(N): a11 = int(data[ptr]) ptr += 1 a12 = int(data[ptr]) ptr += 1 a21 = int(data[ptr]) ptr += 1 a22 = int(data[ptr]) ptr += 1 a11 = a11 % B a12 = a12 % B a21 = a21 % B a22 = a22 % B # Ensure they are in [0, B-1] a11 = (a11 + B) % B a12 = (a12 + B) % B a21 = (a21 + B) % B a22 = (a22 + B) % B current = [[a11, a12], [a21, a22]] # Multiply current matrix with previous prefix (right multiplication) new_prefix = multiply(current, prefix[-1], B) prefix.append(new_prefix) # Process each query for _ in range(Q): L = int(data[ptr]) ptr += 1 R = int(data[ptr]) ptr += 1 x = int(data[ptr]) ptr += 1 y = int(data[ptr]) ptr += 1 if L >= R: x_mod = x % B y_mod = y % B x_mod = (x_mod + B) % B y_mod = (y_mod + B) % B print(x_mod, y_mod) continue if L == 0: M = prefix[R] else: if L >= len(prefix): inv_L = identity() else: inv_L = inverse_matrix(prefix[L], B) # Compute inv_L * prefix[R] M = multiply(inv_L, prefix[R], B) x_in = (x % B + B) % B y_in = (y % B + B) % B new_x = (M[0][0] * x_in + M[0][1] * y_in) % B new_y = (M[1][0] * x_in + M[1][1] * y_in) % B new_x = (new_x + B) % B new_y = (new_y + B) % B print(new_x, new_y) if __name__ == '__main__': main()