結果
問題 |
No.2443 特殊線形群の標準表現
|
ユーザー |
![]() |
提出日時 | 2025-04-24 12:31:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 369 ms / 3,000 ms |
コード長 | 2,721 bytes |
コンパイル時間 | 193 ms |
コンパイル使用メモリ | 82,584 KB |
実行使用メモリ | 172,128 KB |
最終ジャッジ日時 | 2025-04-24 12:32:47 |
合計ジャッジ時間 | 4,642 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import sys def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 B = int(input[ptr]) ptr += 1 Q = int(input[ptr]) ptr += 1 if B == 1: for _ in range(Q): print("0 0") return # Read matrices and mod B matrices = [] for _ in range(N): a = int(input[ptr]) % B ptr += 1 b = int(input[ptr]) % B ptr += 1 c = int(input[ptr]) % B ptr += 1 d = int(input[ptr]) % B ptr += 1 matrices.append((a, b, c, d)) # Compute suffix arrays suffix = [(1, 0, 0, 1)] # suffix[0] is identity for i in range(N): a, b, c, d = matrices[i] prev_a, prev_b, prev_c, prev_d = suffix[-1] new_a = (a * prev_a + b * prev_c) % B new_b = (a * prev_b + b * prev_d) % B new_c = (c * prev_a + d * prev_c) % B new_d = (c * prev_b + d * prev_d) % B suffix.append((new_a, new_b, new_c, new_d)) # Compute inv_suffix arrays inv_suffix = [(1, 0, 0, 1)] # inv_suffix[0] is identity for i in range(N): a, b, c, d = matrices[i] # Compute inverse of A_i mod B inv_a = d % B inv_b = (-b) % B inv_c = (-c) % B inv_d = a % B # Multiply inv_suffix[i] = inv_suffix[i-1] * inv_A_i prev_ia, prev_ib, prev_ic, prev_id = inv_suffix[-1] new_ia = (prev_ia * inv_a + prev_ib * inv_c) % B new_ib = (prev_ia * inv_b + prev_ib * inv_d) % B new_ic = (prev_ic * inv_a + prev_id * inv_c) % B new_id = (prev_ic * inv_b + prev_id * inv_d) % B inv_suffix.append((new_ia, new_ib, new_ic, new_id)) # Process queries for _ in range(Q): L = int(input[ptr]) ptr += 1 R = int(input[ptr]) ptr += 1 x = int(input[ptr]) ptr += 1 y = int(input[ptr]) ptr += 1 if L == R: # No matrices applied z = x % B w = y % B print(f"{z} {w}") continue # Compute the matrix product for [L+1, R] if L == 0: mat = suffix[R] else: # Multiply suffix[R] * inv_suffix[L] sa, sb, sc, sd = suffix[R] isa, isb, isc, isd = inv_suffix[L] a = (sa * isa + sb * isc) % B b = (sa * isb + sb * isd) % B c = (sc * isa + sd * isc) % B d = (sc * isb + sd * isd) % B mat = (a, b, c, d) x_mod = x % B y_mod = y % B z = (mat[0] * x_mod + mat[1] * y_mod) % B w = (mat[2] * x_mod + mat[3] * y_mod) % B print(f"{z} {w}") if __name__ == "__main__": main()