Tích Ma Trận Đoạn
Points
33
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho N ma trận vuông 2×2 với phần tử là số nguyên. Hỗ trợ hai thao tác: thay ma trận thứ i bằng ma trận khác, hoặc tính tích M_l · M_{l+1} · ... · M_r (theo đúng thứ tự) modulo 10^9+7.
Dữ liệu vào
Dòng đầu chứa N và Q. N dòng tiếp theo, dòng thứ i chứa 4 số a b c d mô tả ma trận [[a, b], [c, d]]. Q dòng tiếp theo:
1 i a b c d: thay ma trận thứ i.2 l r: truy vấn.
Dữ liệu ra
Với mỗi truy vấn loại 2, in ra 4 số a b c d của ma trận tích, mỗi số lấy modulo 10^9+7.
Ví dụ
| Input | Output |
|---|---|
| 5 4\n8 8 6 5\n3 2 7 1\n3 7 9 1\n5 2 1 4\n5 6 1 1\n2 4 5\n2 2 5\n1 5 4 6 6 2\n2 4 5 | 27 32 9 10\n936 1094 1260 1460\n32 34 28 14 |
Giới hạn
- 1 ≤ N, Q ≤ 10^5
- 0 ≤ a, b, c, d ≤ 10^9
Community Discussion