結果

問題 No.2443 特殊線形群の標準表現
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:29:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 510 ms / 3,000 ms
コード長 2,449 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 179,632 KB
最終ジャッジ日時 2025-04-24 12:31:05
合計ジャッジ時間 6,560 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    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

    # Read matrices
    A = []
    for _ in range(N):
        a11 = int(input[ptr])
        ptr += 1
        a12 = int(input[ptr])
        ptr += 1
        a21 = int(input[ptr])
        ptr += 1
        a22 = int(input[ptr])
        ptr += 1
        mat = [[a11 % B, a12 % B], [a21 % B, a22 % B]]
        A.append(mat)

    # Precompute prefix products
    if B == 1:
        for _ in range(Q):
            print(0, 0)
        return

    # Compute prefix products where prefix[i] = A_i * A_{i-1} * ... * A_1 mod B
    prefix = []
    prefix.append([[1, 0], [0, 1]])  # prefix[0] is identity matrix
    for i in range(1, N + 1):
        a = A[i - 1]
        prev = prefix[i - 1]
        # Compute a * prev
        a00, a01 = a[0]
        a10, a11 = a[1]
        p00, p01 = prev[0]
        p10, p11 = prev[1]
        c00 = (a00 * p00 + a01 * p10) % B
        c01 = (a00 * p01 + a01 * p11) % B
        c10 = (a10 * p00 + a11 * p10) % B
        c11 = (a10 * p01 + a11 * p11) % B
        prefix.append([[c00, c01], [c10, c11]])

    # Process each query
    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
        y_mod = y % B

        if L == R:
            print(x_mod % B, y_mod % B)
            continue

        # Compute inv of prefix[L]
        mat_L = prefix[L]
        a, b = mat_L[0]
        c, d = mat_L[1]
        inv_a = d % B
        inv_b = (-b) % B
        inv_c = (-c) % B
        inv_d = a % B
        inv_L = [[inv_a, inv_b], [inv_c, inv_d]]

        # Compute M = prefix[R] * inv_L mod B
        mat_R = prefix[R]
        m00 = (mat_R[0][0] * inv_L[0][0] + mat_R[0][1] * inv_L[1][0]) % B
        m01 = (mat_R[0][0] * inv_L[0][1] + mat_R[0][1] * inv_L[1][1]) % B
        m10 = (mat_R[1][0] * inv_L[0][0] + mat_R[1][1] * inv_L[1][0]) % B
        m11 = (mat_R[1][0] * inv_L[0][1] + mat_R[1][1] * inv_L[1][1]) % B
        M = [[m00, m01], [m10, m11]]

        # Apply matrix M to (x_mod, y_mod)
        new_x = (M[0][0] * x_mod + M[0][1] * y_mod) % B
        new_y = (M[1][0] * x_mod + M[1][1] * y_mod) % B
        print(new_x, new_y)

if __name__ == '__main__':
    main()
0