MATRIXPOW - Lũy thừa ma trận
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho ma trận vuông ~A~ cấp ~m~ và một số nguyên dương ~n~. Hãy tính ~B = A^n~.
Input
- Dòng đầu chứa hai số nguyên dương ~m~ và ~n~;
- ~m~ dòng sau, dòng thứ ~i~ chứa ~m~ số nguyên ~a_{i1}, a_{i2}, …, a_{im}~. Hai số liên tiếp được ghi cách nhau một dấu cách.
Giới hạn:
- ~1 ≤ m ≤ 100; 1 ≤ n ≤ 10^{18}; 0 ≤ a_{ij} ≤ 10^9~.
Output
- ~m~ dòng của ma trận ~B = A^n~. Các phần tử của ma trận ~B~ được chia cho ~10^9 + 7~ lấy phần dư.
Sample
Input #1
2 2
1 2
3 4
Output #1
7 10
15 22
Problem source: Chuyên Sơn La Online Judge
Bình luận
Kích cỡ ma trận phải tầm ~200~ mới AC :v