AdditionalFile4101.zip

P9417 [POI 2021/2022 R1] Druk

题目背景

译自 XXIX Olimpiada Informatyczna – I etap Druk。

题目描述

给你一个 $n\times m$ 的字符矩形，只含小写英文字母。

你需要制作两块模板，一个是横的（一行 $l$ 列），一个是竖的（$l$ 行一列），$l$ 称为模板长度，上面有完全相同的字符串（从左到右，从上到下，不可翻转）。你需要保证你可以用这两块模板不重不漏地印刷这个字符矩形。

模板的制作方案可能有很多，你只需要输出所有的可行的模板长度即可。

输入格式

第一行两个正整数 $n,m$，表示矩形大小。

接下来是一个 $n$ 行 $m$ 列的字符矩形，只含小写英文字母。

输出格式

第一行一个整数，表示你找到的可行长度的个数。

第二行若干个整数，你找到的所有可行长度。从小到大输出。

输入输出样例 #1

输入 #1

5 8
aabaaaaa
babaabbb
aabaaaaa
aabaaaaa
abaaabaa

输出 #1

1
4

输入输出样例 #2

输入 #2

1 1000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

输出 #2

16
1 2 4 5 8 10 20 25 40 50 100 125 200 250 500 1000

输入输出样例 #3

输入 #3

3 1000
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab

输出 #3

12
2 4 8 10 20 40 50 100 200 250 500 1000

输入输出样例 #4

输入 #4

4 9
aabaaabaa
babababab
aabaaabaa
abaabaaba

输出 #4

1
3

输入输出样例 #5

输入 #5

见附件

输出 #5

0

输入输出样例 #6

输入 #6

见附件

输出 #6

1
4

说明/提示

样例一解释：

样例四解释：

对于所有数据，$1\leq n,m\leq 1000$。

子任务编号	附加限制	分数
1	$n=1,m\leq 1000$	10
2	$n\leq 3,m\leq 1000$	25
3	$n,m\leq 20$	20
4		45

#4101. 「POI 2021/2022 R1」Druk

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXIX Olimpiada Informatyczna – I etap Druk

印刷匠 Bajtazar 收到了一个印刷任务，要求他印刷一块写有文字的牌子。牌子是一个 $n \times m$ 的网格，字母均匀分布在上面。Bajtazar 要用一个印刷模板来完成印刷，这个模板是一个宽度等于一个字母行的长条。印刷的过程是通过若干次把模板放在牌子上，然后在模板上喷涂颜料。注意印刷的时候模板不能超出牌子的边界。

模板要分别准备横向和纵向的两种版本，而且两种版本必须包含相同的文字。Bajtazar 必须用模板精确地印刷牌子上的每一个位置。注意，不能把任何一种版本的模板旋转，否则字母会倒过来印刷。

请你帮助 Bajtazar 告诉他所有可以用来印刷整个牌子的模板的长度。

输入格式

输入的第一行包含两个正整数 $n, m$，分别表示牌子上的字母行数和每行的字母数。接下来的 $n$ 行，每行包含一个长度为 $m$ 的由小写字母字母组成的字符串，表示牌子上从上到下的每一行的内容。

输出格式

输出的第一行应该包含一个整数，表示 Bajtazar 可以用来印刷牌子的模板的长度的数量。第二行应该包含所有这些长度，按照严格递增的顺序，用单个空格隔开。如果第一行输出的是 $0$，那么第二行应该留空。

样例 1

输入

5 8
aabaaaaa
babaabbb
aabaaaaa
aabaaaaa
abaaabaa

输出

1
4

样例 2

见附加文件下 [dru1.in](file:dru1.in) 和 [dru1.out](file:dru1.out)。

该样例满足 $n=1, m=1000$，全部都是字母 $\texttt{a}$。

样例 3

见附加文件下 [dru2.in](file:dru2.in) 和 [dru2.out](file:dru2.out)。

该样例满足 $n=3, m=1000$，每行都是 $\texttt{ababab}\ldots$ 形式的文本。

样例 4

见附加文件下 [dru3.in](file:dru3.in) 和 [dru3.out](file:dru3.out)。

该样例满足 $n=4, m=9$，文本如下图所示：

样例 5

见附加文件下 [dru4.in](file:dru4.in) 和 [dru4.out](file:dru4.out)。

该样例满足 $n=m=1000$，全部都是字母 $\texttt{a}$ 和中间一个字母 $\texttt{c}$，不存在这样的模板。

样例 6

见附加文件下 [dru5.in](file:dru5.in) 和 [dru5.out](file:dru5.out)。

该样例满足 $n=m=1000$，牌子由 和 像国际象棋棋盘一样交替组成 。存在一个模板 $\texttt{abba}$（注意，$\texttt{ab}$ 不是模板）。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$n=1, m \leq 1000$	$10$
$2$	$n \leq 3, m \leq 1000$	$25$
$3$	$n, m \leq 20$	$20$
$4$	$n, m \leq 1000$	$45$