← 返回题目列表

Codeforces · 1192/C

C. 立方字

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

立方体字词是一种特殊类型的填字游戏。构建立方体字时,首先选择一个正整数 $$$a$$$:立方体的边长。然后,你构建一个由 $$$a \times a \times a$$$ 单位立方体组成的大立方体。这个大立方体有 12 条边。然后,丢弃所有不接触大立方体边缘的单位立方体。下图显示了您将通过 $$$a=6$$$ 获得的对象。

最后,为对象中的每个单位立方体分配一个字母。你必须沿着大立方体的每条边得到一个有意义的单词。每个边缘可以在任一方向上读取,并且如果两个读取方向之一给出有意义的单词就足够了。

下图显示了 $$$a=6$$$ 的对象,其中一些单位立方体已经分配了字母。您已经可以沿着大立方体的三个边缘读取“提交”、“接受”和“图灵”一词。

您将获得一个有效单词列表。单词列表中的每个单词都可以出现在有效立方体字的任意​​多个边上。查找并报告可以构造的不同立方体字的数量,以 $$$998,244,353$$$ 为模。

如果一个立方体字可以通过旋转或镜像从另一个立方体字获得,则它们被认为是不同的。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100,000$$$) – 单词数。

然后是 $$$n$$$ 行。每一行都包含一个可以出现在大立方体边缘的单词。每个单词的长度在 3 到 10 之间(含 3 和 10)。

保证所有单词都不同。

输出

输出一个整数,即给定有效单词列表的不同立方体单词的数量以 $$$998,244,353$$$ 为模。

示例

输入 #1

1
radar

输出 #1

1

输入 #2

1
robot

输出 #2

2

输入 #3

2
FLOW
WOLF

输出 #3

2

输入#4

2
baobab
bob

输出#4

4097

输入 #5

3
TURING
SUBMIT
ACCEPT

输出 #5

162

输入 #6

3
MAN1LA
MAN6OS
AN4NAS

输出 #6

114

注意

评分:
子任务 1(21 分):单词仅由字母“a”-“f”(小写)组成

子任务2(29分):单词仅由字母'a' - 'p'(小写)组成

子任务3(34分):单词由字母“a”-“p”(小写)和“A”-“P”(大写)组成

子任务4(16分):单词由字母“a”-“z”(小写)、“A”-“Z”(大写)和数字“0”-“9”组成

在第一个示例中,唯一的可能性是单词“radar”出现在立方体的每个边缘上。

在第二个示例中,有两个立方体,它们只是彼此旋转 - 每个边上都有“robot”一词,两个立方体之间的区别在于左下角是否包含“r”或“t”。

第三个示例与第二个示例类似。我们可以从两个方向读取每个边缘上的单词这一事实并不影响答案。

在第四个示例中,有一个立方体的每条边上都有单词“bob”。还有 $$$2^{12} = 4096$$$ 立方体,每条边上都带有单词“baobab”。 (对于 12 条边中的每一条,我们都有两个可能的方向来出现单词“baobab”。)