#P51182. 「CEOI2019」立方填词
「CEOI2019」立方填词
题目描述
译自 CEOI 2019 Day1 T3「Cubeword」
立方填词是一种特殊的填词游戏。填词之前,你需要选择立方体的边长 ,然后你就可以建立一个有 个单位立方体的立方体了。这个大立方体有 条边。然后,你去掉所有没有接触大立方体边的单位立方体。下图展示了当 时建立的最终立方体。
最后,你需要给剩下的每个单位立方体填上一个字母。对于这个立方体,填词之后,每条边上的单词都应该是有意义的。每条边都可以双向阅读,只要从一个方向读起来有意义即可。
下图展示了当 时的一个立方体。一些单位立方体已经填上了字母。你已经可以沿这个大立方体的三条边读到 SUBMIT
,ACCEPT
和 TURING
三个单词了。
给定一系列有意义的单词,每个单词可以在合法的立方体的任意一条边上出现。求可以构造多少种不同的立方体对 取模。
如果一个立方体可以通过旋转和镜像操作变成另一个立方体,则认为这两个立方体是不同的。
输入格式
第一行一个整数 ,表示单词的个数。
接下来 行,每行一个单词,表示可以在大立方体的边上出现的单词。单词长度大于等于 ,并且小于等于 。
保证所有单词都不同。
输出格式
输出一个整数,表示可以构造的不同立方体数对 取模后的结果。
样例 1
1
radar
1
第一个样例中,唯一一种可能是立方体的所有边上的单词均为 radar
。
1
robot
2
第二个样例中,有两种立方体,其中一个旋转后可以得到另一个立方体。立方体所有边上的单词都是 robot
,两个立方体的不同之处在于左下角的字母是 r
还是 t
。
2
FLOW
WOLF
2
第三个样例与第二个类似,注意阅读方向不会影响答案。
2
baobab
bob
4097
第四个样例中,如果把 bob
填在立方体的每条边上,有一种立方体。还有 种立方体,每条边都填 baobab
(对于 条边中的一条,我们有两种可能的阅读顺序)。
3
TURING
SUBMIT
ACCEPT
162
3
MAN1LA
MAN6OS
AN4NAS
114
数据范围与提示
对于全部数据,。
详细子任务限制及分值如下表:
子任务编号 | 限制 | 分值 |
---|---|---|
单词中只包含小写的 a 到 f |
||
单词中只包含小写的 a 到 p |
||
单词中包含小写的 a 到 p 和大写的 A 到 P |
||
单词中包含小写的 a 到 z ,大写的 A 到 Z 和数字 0 到 9 |