結果
問題 |
No.2443 特殊線形群の標準表現
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()