結果

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

ソースコード

diff # 

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