← 返回题目列表

Codeforces · 1080/E

E. 索尼娅和矩阵美女

中文机器翻译题面 查看原题

索尼娅最近过生日。她看到大小为 $$$n\times m$$$ 的矩阵,由小写拉丁字母组成。我们假设行从下到上按从 $$$1$$$ 到 $$$n$$$ 的整数进行编号,列从左到右从 $$$1$$$ 到 $$$m$$$ 进行编号。

让我们调用该矩阵的子矩阵 $$$(i_1, j_1, i_2, j_2)$$$ $$$(1\leq i_1\leq i_2\leq n; 1\leq j_1\leq j_2\leq m)$$$ 元素 $$$a_{ij}$$$,使得 $$$i_1\leq i\leq i_2$$$ 和 $$$j_1\leq j\leq j_2$$$。索尼娅指出,如果我们能够独立地对每行(而不是列)中的字符进行重新排序,以便该子矩阵的所有行和列形成回文,那么子矩阵就是美丽的。

让我们回想一下,如果一个字符串从左到右和从右到左读取相同,则称为回文。例如,字符串 $$$abacaba、bcaacb、a$$$ 是回文,而字符串 $$$abca、acbba、ab$$$ 则不是回文。

帮助索尼娅找到美丽子矩阵的数量。如果有一个元素只属于一个子矩阵,则子矩阵是不同的。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(1\leq n, m\leq 250)$$$ — 矩阵维度。

接下来的 $$$n$$$ 行包含 $$$m$$$ 小写拉丁字母。

输出

打印一个整数——美丽子矩阵的数量。

示例

输入 #1

1 3
aba

输出 #1

4

输入 #2

2 3
aca
aac

输出 #2

11

输入 #3

3 5
accac
aaaba
cccaa

输出 #3

43

注意

在第一个示例中,以下子矩阵很漂亮: $$$((1, 1), (1, 1)); ((1, 2), (1, 2));$$$ $$$((1, 3), (1, 3)); ((1, 1), (1, 3))$$$。

在第二个示例中,所有由一个元素组成的子矩阵以及以下内容都很漂亮: $$$((1, 1), (2, 1));$$$ $$$((1, 1), (1, 3)); ((2, 1), (2, 3)); ((1, 1), (2, 3)); ((2, 1), (2, 2))$$$。

一些漂亮的子矩阵是: $$$((1, 1), (1, 5)); ((1, 2), (3, 4));$$$ $$$((1, 1), (3, 5))$$$。

子矩阵 $$$((1, 1), (3, 5))$$$ 很漂亮,因为它可以重新排序为:

在这样的矩阵中,每一行和每一列都形成回文。