AT_abc420_f.[ABC420F] kirinuki

给定一个 $N \times M$ 的网格。每个格子中包含 . 或 #。
关于每个格子的符号信息由 $N$ 个字符串 $S_1,S_2,\dots,S_N$ 给出，其中 $S_i$ 的第 $j$ 个字符表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子中写的符号。
请你计算有多少个至多包含 $K$ 个格子的矩形区域，且该区域内所有格子均为 .。

形式化地，计算满足以下条件的整数四元组 $(l_x,r_x,l_y,r_y)$ 的个数：

• $1 \le l_x \le r_x \le N$
• $1 \le l_y \le r_y \le M$
• $(r_x-l_x+1) \times (r_y-l_y+1) \le K$
• 对于所有满足 $l_x \le i \le r_x$ 且 $l_y \le j \le r_y$ 的整数对 $(i,j)$，第 $i$ 行第 $j$ 列的格子中为 .。

输入按如下格式从标准输入给出：

$N$ $M$ $K$
$S_1$
$S_2$
$\vdots$
$S_N$

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

样例解释 1

需要计数的 $19$ 个矩形区域如下：

• 由 $(l_x,r_x,l_y,r_y) = (1,2,2,3)$ 表示的矩形区域
• 由 $(l_x,r_x,l_y,r_y) = (2,3,1,2)$ 表示的矩形区域
• 由 $(l_x,r_x,l_y,r_y) = (2,2,1,3)$ 表示的矩形区域
• 由 $(l_x,r_x,l_y,r_y) = (1,3,2,2)$ 表示的矩形区域
• $4$ 个仅包含 . 的 $1$ 行 $2$ 列的矩形区域
• $4$ 个仅包含 . 的 $2$ 行 $1$ 列的矩形区域
• $7$ 个仅包含 . 的 $1$ 行 $1$ 列的矩形区域

数据范围

• $N$、$M$、$K$ 均为整数。
• $1 \le N, M \le 5 \times 10^5$
• $1 \le N \times M \le 5 \times 10^6$
• $1 \le K \le N \times M$
• $S_i$ 是长度为 $M$ 的、仅包含 . 和 # 的字符串。

由 ChatGPT 4.1 翻译