← 返回题目列表

Codeforces · 1533/H

H. 子矩阵

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

给定矩阵 $$$s$$$,其中包含 $$$n$$$ 行和 $$$m$$$ 列。矩阵的每个元素都是 $$$5$$$ 的第一个拉丁字母(大写)之一。

对于每个 $$$k$$$ ($$$1 \le k \le 5$$$) 计算恰好包含 $$$k$$$ 不同字母的子矩阵的数量。回想一下,矩阵 $$$s$$$ 的子矩阵是可以从 $$$s$$$ 删除几个(可能零)第一行、几个(可能零)最后行、几个(可能零)第一列和几个(可能零)最后列后获得的矩阵。如果某个子矩阵可以通过两种或多种方式从$$$s$$$获得,则必须计算该子矩阵相应的次数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 800$$$)。

接下来是 $$$n$$$ 行,每行包含字符串 $$$s_i$$$ ($$$|s_i| = m$$$) — $$$i$$$ 矩阵的第行。

输出

对于每个 $$$k$$$ ($$$1 \le k \le 5$$$) 打印一个整数 - 恰好包含 $$$k$$$ 不同字母的子矩阵的数量。

示例

输入 #1

2 3
ABB
ABA

输出 #1

9 9 0 0 0

输入 #2

6 6
EDCECE
EDDCEB
ACCECC
BAEEDC
DDDDEC
DDAEAD

输出 #2

56 94 131 103 57

输入 #3

3 10
AEAAEEEEEC
CEEAAEEEEE
CEEEEAACAA

输出 #3

78 153 99 0 0