結果

問題 No.2443 特殊線形群の標準表現
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:58:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,281 bytes
コンパイル時間 280 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 165,664 KB
最終ジャッジ日時 2025-03-20 20:58:43
合計ジャッジ時間 4,474 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0

    N = int(input[idx])
    B = int(input[idx + 1])
    Q = int(input[idx + 2])
    idx += 3

    matrices = []
    for _ in range(N):
        a11 = int(input[idx]) % B
        a12 = int(input[idx + 1]) % B
        a21 = int(input[idx + 2]) % B
        a22 = int(input[idx + 3]) % B
        matrices.append((a11, a12, a21, a22))
        idx += 4

    # Precompute prefix products, multiplying from the right
    prefix = [(1, 0, 0, 1)]  # identity matrix for prefix[0]
    for i in range(N):
        current = matrices[i]
        prev = prefix[i]
        # Multiply current matrix (right) with previous prefix (left)
        a, b, c, d = prev
        a_curr, b_curr, c_curr, d_curr = current
        new_a = (a_curr * a + b_curr * c) % B
        new_b = (a_curr * b + b_curr * d) % B
        new_c = (c_curr * a + d_curr * c) % B
        new_d = (c_curr * b + d_curr * d) % B
        prefix.append((new_a, new_b, new_c, new_d))

    def inverse_matrix(m):
        a, b, c, d = m
        inv_a = d % B
        inv_b = (-b) % B
        inv_c = (-c) % B
        inv_d = a % B
        return (inv_a, inv_b, inv_c, inv_d)

    def multiply(m1, m2):
        a1, b1, c1, d1 = m1
        a2, b2, c2, d2 = m2
        new_a = (a1 * a2 + b1 * c2) % B
        new_b = (a1 * b2 + b1 * d2) % B
        new_c = (c1 * a2 + d1 * c2) % B
        new_d = (c1 * b2 + d1 * d2) % B
        return (new_a, new_b, new_c, new_d)

    results = []
    for _ in range(Q):
        L = int(input[idx])
        R = int(input[idx + 1])
        x = int(input[idx + 2])
        y = int(input[idx + 3])
        idx += 4

        if L == R:
            z = x % B
            w = y % B
            results.append(f"{z % B} {w % B}")
            continue

        if B == 1:
            results.append("0 0")
            continue

        if L == 0:
            M = prefix[R]
        else:
            inv_L = inverse_matrix(prefix[L])
            M = multiply(inv_L, prefix[R])

        x_mod = x % B
        y_mod = y % B

        a, b, c, d = M
        z = (a * x_mod + b * y_mod) % B
        w = (c * x_mod + d * y_mod) % B

        results.append(f"{z % B} {w % B}")

    print('\n'.join(results))

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