CF253D Table with Letters - 2

Vasya 最近开始学习英语。现在，他需要记住如何书写英文字母。有些字母他还不太确定，所以决定进行一些练习。 他找到一张方格纸，在上面随意地书写英文字母。最终，Vasya 写下了 $n$ 行，每行包含 $m$ 个字符。这样，他得到了一个 $n \times m$ 的矩形表格，每个格子中包含一个英文字母。我们将表格的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。 之后，Vasya 看着自己写下的矩形表格，想知道有多少个满足以下两个条件的子矩形： - 子矩形中最多包含 $k$ 个字母 "a"； - 子矩形四个角上的字母都相同。 形式化地说，子矩形由四个整数 $x_1, y_1, x_2, y_2$ 定义，满足 $1 \leq x_1 < x_2 \leq n$，$1 \leq y_1 < y_2 \leq m$。那么，这个子矩形包含所有满足 $x_1 \leq x \leq x_2,\ y_1 \leq y \leq y_2$ 的格子 $(x, y)$。子矩形的四个角分别是 $(x_1, y_1)$、$(x_1, y_2)$、$(x_2, y_1)$ 和 $(x_2, y_2)$。 Vasya 写字已经很累了，因此请你帮他计算符合条件的子矩形有多少个。

第一行包含三个整数 $n, m, k$，满足 $2 \leq n, m \leq 400$，$0 \leq k \leq n\cdot m$。 接下来 $n$ 行，每行包含 $m$ 个小写英文字母，表示矩形表格。

输出一个整数，表示符合条件的子矩形的数量。

在第一个样例中，有两个符合条件的子矩形：第一个的左上角为 $(2,2)$，右下角为 $(3,3)$；第二个的左上角为 $(2,1)$，右下角为 $(3,4)$。 由 ChatGPT 5 翻译