Đếm ma trận con có tổng bằng K

Arrays Buổi 15 — Prefix Sum & Difference Array prefix-sum
Points
68
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho ma trận số nguyên kích thước $N \times M$ (có thể chứa số âm, số $0$, số dương) và một số nguyên $K$. Hãy đếm số lượng ma trận con hình chữ nhật không rỗng có tổng các phần tử đúng bằng $K$.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $N, M, K$. $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên.

Dữ liệu ra

In ra một số nguyên duy nhất là số lượng ma trận con thỏa mãn.

Ví dụ
Input Output
3 3 0
0 1 0
1 1 1
0 1 0
4
2 2 0
1 -1
-1 1
5
Giới hạn

$1 \le N, M \le 250$, $|A_{i,j}| \le 10^5$, $|K| \le 10^9$.

Draft saved