結果
問題 |
No.2443 特殊線形群の標準表現
|
ユーザー |
![]() |
提出日時 | 2025-04-24 12:31:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,291 ms / 3,000 ms |
コード長 | 2,936 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 82,412 KB |
実行使用メモリ | 205,252 KB |
最終ジャッジ日時 | 2025-04-24 12:33:09 |
合計ジャッジ時間 | 13,631 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import sys class SegmentTree: def __init__(self, data, mod): self.n = len(data) self.mod = mod self.tree = [[] for _ in range(4 * self.n)] self.data = data self.build(1, 0, self.n - 1) def build(self, node, start, end): if start == end: self.tree[node] = self.data[start] else: mid = (start + end) // 2 self.build(2 * node, start, mid) self.build(2 * node + 1, mid + 1, end) self.tree[node] = self.multiply(self.tree[2 * node + 1], self.tree[2 * node]) def multiply(self, a, b): res = [[0] * 2 for _ in range(2)] res[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % self.mod res[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % self.mod res[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % self.mod res[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % self.mod return res def query_range(self, node, start, end, l, r): if r < start or end < l: return [[1, 0], [0, 1]] if l <= start and end <= r: return self.tree[node] mid = (start + end) // 2 left = self.query_range(2 * node, start, mid, l, r) right = self.query_range(2 * node + 1, mid + 1, end, l, r) return self.multiply(right, left) def query(self, l, r): if l > r: return [[1, 0], [0, 1]] return self.query_range(1, 0, self.n - 1, l, r) 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 matrices = [] for _ in range(N): a = int(input[ptr]) ptr += 1 b = int(input[ptr]) ptr += 1 c = int(input[ptr]) ptr += 1 d = int(input[ptr]) ptr += 1 a_mod = a % B b_mod = b % B c_mod = c % B d_mod = d % B matrices.append([[a_mod, b_mod], [c_mod, d_mod]]) st = SegmentTree(matrices, B) 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 x_mod = x % B if x_mod < 0: x_mod += B y_mod = y % B if y_mod < 0: y_mod += B if L == R: print(x_mod, y_mod) continue code_L = L code_R = R - 1 product = st.query(code_L, code_R) z = (product[0][0] * x_mod + product[0][1] * y_mod) % B w = (product[1][0] * x_mod + product[1][1] * y_mod) % B z = z % B if z < 0: z += B w = w % B if w < 0: w += B print(z, w) if __name__ == '__main__': main()