Hình chữ nhật chi hết cho 9
Xem PDF
Điểm:
1400
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một bảng số kích thước \(N \times M\). Hãy đếm số lượng hình chữ nhật con của bảng số sao cho tổng các phần tử trong hình chữ nhật đó chia hết cho \(9\).
Input
- Dòng 1: Hai số nguyên dương \(N, M\) (\(1 \le N, M \le 400\)).
- \(N\) dòng tiếp theo: Mỗi dòng gồm \(M\) số nguyên \(A_{i,j}\) (\(0 \le A_{i,j} \le 10^9\)).
Output
- Một số nguyên duy nhất là kết quả bài toán.
Example
Test 1
Input
2 2
2 7
9 0Output
5Note
Các hình chữ nhật con có tổng chia hết cho \(9\) là: \(1\) hình hàng \(1\) (tổng \(9\)), \(2\) hình kích thước \(1 \times 1\) (tổng \(9\) và \(0\)), \(1\) hình hàng \(2\) (tổng \(9\)), và \(1\) hình toàn bảng (tổng \(18\)). Tổng cộng \(5\) hình.
Scoring
- Subtask \(1\) (\(30\%\) số điểm): \(N, M \le 50\).
- Subtask \(2\) (\(70\%\) số điểm): \(N, M \le 400\).
Bình luận