結果

問題 No.2443 特殊線形群の標準表現
コンテスト
ユーザー qwewe
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0