結果
問題 | No.2443 特殊線形群の標準表現 |
ユーザー |
|
提出日時 | 2023-08-25 22:36:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 995 ms / 3,000 ms |
コード長 | 912 bytes |
コンパイル時間 | 421 ms |
コンパイル使用メモリ | 81,772 KB |
実行使用メモリ | 147,964 KB |
最終ジャッジ日時 | 2024-12-24 09:57:11 |
合計ジャッジ時間 | 9,528 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
def mat_mul(a, b, MOD):"""a: 行列(2次元配列)I*Jb: 行列(2次元配列)J*K"""I, J, K = len(a), len(b[0]), len(b)c = [[0] * J for _ in range(I)]for i in range(I):for j in range(J):for k in range(K):c[i][j] += a[i][k] * b[k][j]c[i][j] %= MODreturn cN, B, Q = map(int, input().split())A = []cumA = [[[1, 0], [0, 1]]]cumA_inv = [[[1, 0], [0, 1]]]for _ in range(N):An = [list(map(int, input().split())) for _ in range(2)]A_inv = [[An[1][1], -An[0][1]], [-An[1][0], An[0][0]]]cumA.append(mat_mul(An, cumA[-1], B))cumA_inv.append(mat_mul(cumA_inv[-1], A_inv, B))ans = []for _ in range(Q):L, R, x, y = map(int, input().split())C = mat_mul(cumA[R], cumA_inv[L], B)z = (C[0][0]*x+C[0][1]*y) % Bw = (C[1][0]*x+C[1][1]*y) % Bans.append((z, w))for c in ans:print(*c)