AT_abc461_d [ABC461D] Count Subgrid Sum = K

有一个 $H \times W$ 的网格，每个格子里写有一个整数 $0$ 或 $1$。 每个格子中的整数信息通过 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \dots, S_H$ 给出。如果 $S_i$ 的第 $j$ 个字符是 `0`，那么第 $i$ 行第 $j$ 列的格子中写的是 $0$；如果是 `1`，写的是 $1$。 请计算有多少个矩形区域，其区域内所有格子中整数的和等于 $K$。 更正式地说，计算有多少组整数四元组 $(r_1, c_1, r_2, c_2)$ 满足如下所有条件： - $1 \le r_1 \le r_2 \le H$ - $1 \le c_1 \le c_2 \le W$ - 所有满足 $r_1 \le i \le r_2, c_1 \le j \le c_2$ 的 $(i, j)$，其所对应格子里的整数之和正好等于 $K$。

输入从标准输入读取，格式如下： > $H$ $W$ $K$ $S_1$ $S_2$ $\vdots$ $S_H$

输出满足条件的矩形区域个数。

## 样例解释 1 有八个矩形区域，其区域内所有格子中整数的和等于 $K$： - 从第 $1$ 行到第 $2$ 行，第 $1$ 列到第 $2$ 列的矩形区域 - 从第 $1$ 行到第 $2$ 行，第 $1$ 列到第 $3$ 列的矩形区域 - 从第 $1$ 行到第 $2$ 行，第 $2$ 列到第 $4$ 列的矩形区域 - 从第 $1$ 行到第 $3$ 行，第 $2$ 列到第 $3$ 列的矩形区域 - 从第 $1$ 行到第 $3$ 行，第 $3$ 列到第 $4$ 列的矩形区域 - 从第 $2$ 行到第 $2$ 行，第 $1$ 列到第 $4$ 列的矩形区域 - 从第 $2$ 行到第 $3$ 行，第 $1$ 列到第 $2$ 列的矩形区域 - 从第 $2$ 行到第 $3$ 行，第 $2$ 列到第 $3$ 列的矩形区域 ## 限制 - $H$ 和 $W$ 是 $1$ 到 $500$ 之间的整数。 - $K$ 是 $0$ 到 $HW$ 之间的整数。 - $S_i$ 是长度为 $W$ 的、仅由 `0` 和 `1` 组成的字符串。 由 ChatGPT 5 翻译