結果

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

ソースコード

diff # 

import sys

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

    if B == 1:
        for _ in range(Q):
            print("0 0")
        return

    # Read matrices and mod B
    matrices = []
    for _ in range(N):
        a = int(input[ptr]) % B
        ptr += 1
        b = int(input[ptr]) % B
        ptr += 1
        c = int(input[ptr]) % B
        ptr += 1
        d = int(input[ptr]) % B
        ptr += 1
        matrices.append((a, b, c, d))

    # Compute suffix arrays
    suffix = [(1, 0, 0, 1)]  # suffix[0] is identity
    for i in range(N):
        a, b, c, d = matrices[i]
        prev_a, prev_b, prev_c, prev_d = suffix[-1]
        new_a = (a * prev_a + b * prev_c) % B
        new_b = (a * prev_b + b * prev_d) % B
        new_c = (c * prev_a + d * prev_c) % B
        new_d = (c * prev_b + d * prev_d) % B
        suffix.append((new_a, new_b, new_c, new_d))

    # Compute inv_suffix arrays
    inv_suffix = [(1, 0, 0, 1)]  # inv_suffix[0] is identity
    for i in range(N):
        a, b, c, d = matrices[i]
        # Compute inverse of A_i mod B
        inv_a = d % B
        inv_b = (-b) % B
        inv_c = (-c) % B
        inv_d = a % B
        # Multiply inv_suffix[i] = inv_suffix[i-1] * inv_A_i
        prev_ia, prev_ib, prev_ic, prev_id = inv_suffix[-1]
        new_ia = (prev_ia * inv_a + prev_ib * inv_c) % B
        new_ib = (prev_ia * inv_b + prev_ib * inv_d) % B
        new_ic = (prev_ic * inv_a + prev_id * inv_c) % B
        new_id = (prev_ic * inv_b + prev_id * inv_d) % B
        inv_suffix.append((new_ia, new_ib, new_ic, new_id))

    # Process queries
    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:
            # No matrices applied
            z = x % B
            w = y % B
            print(f"{z} {w}")
            continue

        # Compute the matrix product for [L+1, R]
        if L == 0:
            mat = suffix[R]
        else:
            # Multiply suffix[R] * inv_suffix[L]
            sa, sb, sc, sd = suffix[R]
            isa, isb, isc, isd = inv_suffix[L]
            a = (sa * isa + sb * isc) % B
            b = (sa * isb + sb * isd) % B
            c = (sc * isa + sd * isc) % B
            d = (sc * isb + sd * isd) % B
            mat = (a, b, c, d)

        x_mod = x % B
        y_mod = y % B
        z = (mat[0] * x_mod + mat[1] * y_mod) % B
        w = (mat[2] * x_mod + mat[3] * y_mod) % B
        print(f"{z} {w}")

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