LOJ100 - Nhân 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
Input:
stdin
Output:
stdout
Tác giả:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, JavaScript, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho 2 ma trận ~A~ có kích thước ~n~ x ~p~ và ma trận ~B~ có kích thước ~p~ x ~m~. Hãy tính kết quả của ~A~ x ~B~.
Input
- Dòng đầu tiên là 3 số nguyên dương ~n, p, m~
- ~n~ dòng tiếp theo, mỗi dòng là ~p~ số nguyên - một hàng của ma trận ~A~
- ~p~ dòng tiếp theo, mỗi dòng là ~m~ số nguyên - một hàng của ma trận ~B~
Output
- Đưa ra ~n~ hàng, mỗi hàng có ~m~ số nguyên - là kết quả của phép nhân ma trận ~A~ x ~B~. Bởi vì giá trị của phép nhân có thể rất lớn, do đó mỗi giá trị trong ma trận kết quả sẽ phải là kết quả của phép chia lấy dư cho ~10^9 + 7~.
Sample
Input #1
3 4 5
-2 -8 -9 8
-10 0 6 -8
-10 -6 6 9
4 -7 5 -5 9
10 -2 -10 5 5
-3 -7 -3 8 -2
-6 7 7 3 -2
Output #1
999999898 149 153 999999929 999999951
999999997 999999979 999999883 74 999999921
999999835 103 55 95 999999857
Ràng buộc
~ 1 \le n, p, m \le 500~, ~-10^9 \le A_{ij}, B_{ij} \le 10^9~
Bình luận
Bài này thay vì mọi người để ~c[i][j] = ((c[i][j] + a[i][k] * b[k][j])~ % ~mod + mod)~ % ~mod~
thì mọi người có thể để là ~c[i][j] = (c[i][j] + a[i][k] * b[k][j] + MM)~ % ~mod~
Với ~MM = mod * mod~
thì code có thể chạy nhanh hơn rất nhiều
orz muôn năm
Ouput #1 sai phải không mọi người.
đúng á fen, spam nộp đi là AC :))