結果

問題 No.2443 特殊線形群の標準表現
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:29:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 420 ms / 3,000 ms
コード長 1,993 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 81,936 KB
実行使用メモリ 154,992 KB
最終ジャッジ日時 2025-04-24 12:31:06
合計ジャッジ時間 5,142 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def multiply(a, b, B):
    a00, a01 = a[0][0], a[0][1]
    a10, a11 = a[1][0], a[1][1]
    b00, b01 = b[0][0], b[0][1]
    b10, b11 = b[1][0], b[1][1]
    c00 = (a00 * b00 + a01 * b10) % B
    c01 = (a00 * b01 + a01 * b11) % B
    c10 = (a10 * b00 + a11 * b10) % B
    c11 = (a10 * b01 + a11 * b11) % B
    return [[c00, c01], [c10, c11]]

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

    prefix_product = [[[1, 0], [0, 1]]]  # prefix_product[0]

    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
        current_A = [[a_mod, b_mod], [c_mod, d_mod]]
        prev = prefix_product[-1]
        new_mat = multiply(current_A, prev, B)
        prefix_product.append(new_mat)

    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:
            x_mod = (x % B + B) % B
            y_mod = (y % B + B) % B
            print(x_mod, y_mod)
            continue

        ML = prefix_product[L]
        MR = prefix_product[R]

        a, b = ML[0][0], ML[0][1]
        c, d = ML[1][0], ML[1][1]

        inv_a = d % B
        inv_b = (-b) % B
        inv_c = (-c) % B
        inv_d = a % B
        inv_ML = [[inv_a, inv_b], [inv_c, inv_d]]

        P = multiply(MR, inv_ML, B)

        x_mod = (x % B + B) % B
        y_mod = (y % B + B) % B

        z = (P[0][0] * x_mod + P[0][1] * y_mod) % B
        w = (P[1][0] * x_mod + P[1][1] * y_mod) % B

        z = (z + B) % B
        w = (w + B) % B

        print(z, w)

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