divide and conquer，简单分治题。
显然可以做二维前缀和，考虑令矩阵 \((l_x-1,r_x,l_y-1,r_y)\to (l_x,r_x,l_y,r_y)\)，方便统计答案，其实就是左端点减一。
考虑现在按照 \(x\) 坐标分治，计算所有跨过 \(x=\text{mid}\) 的矩形的贡献。枚举矩形顶点的 \(y\) 坐标范围 \([i,j]\)，维护 \(s_{0/1,l}\) 表示当前纵坐标 \([i,j]\) 下，直线 \(x=\text{mid}\) 左方/右方，使得矩阵 \((p,\text{mid},i,j)\) 或者 \((\text{mid},p,i,j)\) 中 \(1\) 的个数小于 \(l\) 的最大/小的 \(p\) 值。当我们求出 \(s\) 后，可以简单地算出 \([i,j]\) 的贡献，为 \(\sum\limits_l(s_{0,l} - s_{0,l+1})(s_{1,k-l+1} - s_{1,k-l})\)。
显然地，当 \(i\) 固定时，随着 \(j\) 的增大，\(s_{0,l}\) 会越来越大，而 \(s_{1,l}\) 会越来越小。可以用双指针维护。复杂度 \(O(km^2n\log n)\)。显然过不了。
考虑到 \(m^2\) 比较大，所以每次选择 \(n,m\) 中更大的一个来分治，复杂度 \(O(kmn\log n)\)。
const int maxn = 3e3 + 300;
int n, m, k, ans, a[maxn][maxn], s[2][maxn];
char c[maxn];
int calc(int xl, int xr, int yl, int yr) { return a[xr][yr] + a[xl][yl] - a[xl][yr] - a[xr][yl]; }
void conq(int xl, int xr, int yl, int yr) {
if (xl == xr || yl == yr) return;
if (xl == xr - 1 && yl == yr - 1) return ans += (calc(xl, xr, yl, yr) == k), void();
if (xr - xl > yr - yl) {
int mid = (xl + xr) >> 1;
for (int i = yl; i <= yr - 1; i++) {
s[0][0] = s[1][0] = mid;
for (int j = 1; j <= k + 1; j++)
s[0][j] = xl, s[1][j] = xr;
for (int j = i + 1; j <= yr; j++) {
for (int l = 1; l <= k + 1; l++) {
while (calc(s[0][l], mid, i, j) >= l) s[0][l]++;
while (calc(mid, s[1][l], i, j) >= l) s[1][l]--;
}
for (int l = 0; l <= k; l++)
ans += (s[0][l] - s[0][l + 1]) * (s[1][k - l + 1] - s[1][k - l]);
}
}
conq(xl, mid, yl, yr);
conq(mid, xr, yl, yr);
} else {
int mid = (yl + yr) >> 1;
for (int i = xl; i <= xr - 1; i++) {
s[0][0] = s[1][0] = mid;
for (int j = 1; j <= k + 1; j++)
s[0][j] = yl, s[1][j] = yr;
for (int j = i + 1; j <= xr; j++) {
for (int l = 1; l <= k + 1; l++) {
while (calc(i, j, s[0][l], mid) >= l) s[0][l]++;
while (calc(i, j, mid, s[1][l]) >= l) s[1][l]--;
}
for (int l = 0; l <= k; l++)
ans += (s[0][l] - s[0][l + 1]) * (s[1][k - l + 1] - s[1][k - l]);
}
}
conq(xl, xr, yl, mid);
conq(xl, xr, mid, yr);
}
}
signed main() {
n = read(), m = read(), k = read();
for (int i = 1; i <= n; i++) {
scanf("%s", c + 1);
for (int j = 1; j <= m; j++) a[i][j] = c[j] - '0';
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] += a[i][j - 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] += a[i - 1][j];
conq(0, n, 0, m);
write(ans);
return 0;
}