[AdditionalFile5408.zip](file://AdditionalFile5408.zip?type=additional_file)

#5408. 「OOI 2020 Day 2」拉丁方阵

标签: 传统 | 时间限制: 10000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2020 Day2 T4 「Латинский квадрат / Latin Squares」。

克里斯喜欢解决各种谜题。最近，他了解了数独游戏，其理念基于拉丁方阵。大小为 $k \times k$ 的表格被称为拉丁方阵，如果表格中不同元素的数量为 $k$，且每行和每列中都没有两个相同的元素。

例如，以下是拉丁方阵的示例：

$\begin{array}{|c|c|} \hline \text{A} & \text{B} \\ \hline \text{B} & \text{A} \\ \hline \end{array}$，$\begin{array}{|c|c|c|} \hline \text{S} & \text{P} & \text{R} \\ \hline \text{R} & \text{S} & \text{P} \\ \hline \text{P} & \text{R} & \text{S} \\ \hline \end{array}$ 和 $\begin{array}{|c|} \hline \text{Q} \\ \hline \end{array}$ 是拉丁方阵，而 $\begin{array}{|c|c|c|} \hline \text{A} & \text{B} & \text{C} \\ \hline \text{C} & \text{C} & \text{A} \\ \hline \text{C} & \text{A} & \text{B} \\ \hline \end{array}$，$\begin{array}{|c|c|c|} \hline \text{A} & \text{B} & \text{C} \\ \hline \text{D} & \text{C} & \text{A} \\ \hline \text{C} & \text{A} & \text{B} \\ \hline \end{array}$ 和 $\begin{array}{|c|c|c|} \hline \text{A} & \text{B} & \text{C} \\ \hline \text{C} & \text{A} & \text{B} \\ \hline \end{array}$ 不是。

克里斯想基于拉丁方阵设计一个新的谜题。然而，他手头只有一个旧的模板，是一个大小为 $n \times m$ 的表格。克里斯希望从这个模板中切出一块连续的部分，使其成为一个拉丁方阵。他能有多少种方式做到这一点？两种方式被认为是不同的，如果存在一个模板单元格在一种情况下属于切割部分，而在另一种情况下不属于切割部分。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 2000)$，表示模板的尺寸。

接下来的 $n$ 行描述模板，每行包含一个长度为 $2 \cdot m$ 的字符串 $s_i$，由 ASCII 码在 $33$ 到 $126$ 之间的字符组成。模板中第 $i$ 行第 $j$ 列的单元格包含字符对 $s_{i, 2 \cdot j - 1}$ 和 $s_{i, 2 \cdot j}$ $(1 \leq i \leq n, 1 \leq j \leq m)$。模板中两个单元格的元素相等，当且仅当这两个单元格中的字符对相同。有关输入数据的详细说明，请参见备注。

输出格式

输出一个整数，即从模板中切割出拉丁方阵的方式数量。

样例 1

输入

4 5
AABBAAAACC
BBAABBCCAA
AABBCCAABB
BBCCAABBCC

输出

26

在第一个样例中，除了 $20$ 种切割出 $1 \times 1$ 拉丁方阵的方式外，还有以下 $6$ 种方式切割出拉丁方阵：

样例 2

输入

5 10
!"#$%&’()*+,-./01234
56789:;<=>?@ABCDEFGH
IJKLMNOPQRSTUVWXYZ[\
]^_‘abcdefghijklmnop
qrstuvwxyz{|}~!"#$%&

输出

50

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。