Cubeword

题意翻译

【**题目描述**】 立方填词是一种特殊的填词游戏。填词之前，你需要选择立方体的边长 $a$，然后你就可以建立一个有 $a^3$个单位立方体的立方体了。这个大立方体有 $12$ 条边。然后，你去掉所有没有接触大立方体边的单位立方体。下图展示了当 $a=6$ 时建立的最终立方体。  最后，你需要给剩下的每个单位立方体填上一个字母。对于这个立方体，填词之后，每条边上的单词都应该是有意义的。每条边都可以双向阅读，只要从一个方向读起来有意义即可。 下图展示了当 $a=6$ 时的一个立方体。一些单位立方体已经填上了字母。你已经可以沿这个大立方体的三条边读到 `SUBMIT`，`ACCEPT` 和 `TURING` 三个单词了。  给定一系列有意义的单词，每个单词可以在合法的立方体的任意一条边上出现。求可以构造多少种不同的立方体对 $998244353$ 取模。 如果一个立方体可以通过旋转和镜像操作变成另一个立方体，则认为这两个立方体是不同的。 【**输入格式**】 第一行一个整数 $n$，表示单词的个数。 接下来 $n$ 行，每行一个单词，表示可以在大立方体的边上出现的单词。单词长度大于等于 $3$，并且小于等于 $10$。 保证所有单词都不同。 【**输出格式**】 输出一个整数，表示可以构造的不同立方体数对 $998244353$ 取模后的结果。

题目描述

A cubeword is a special type of a crossword. When building a cubeword, you start by choosing a positive integer $ a $ : the side length of the cube. Then, you build a big cube consisting of $ a \times a \times a $ unit cubes. This big cube has 12 edges. Then, you discard all unit cubes that do not touch the edges of the big cube. The figure below shows the object you will get for $ a=6 $ . Finally, you assign a letter to each of the unit cubes in the object. You must get a meaningful word along each edge of the big cube. Each edge can be read in either direction, and it is sufficient if one of the two directions of reading gives a meaningful word. The figure below shows the object for $ a=6 $ in which some unit cubes already have assigned letters. You can already read the words 'SUBMIT', 'ACCEPT' and 'TURING' along three edges of the big cube. You are given a list of valid words. Each word from the wordlist may appear on arbitrarily many edges of a valid cubeword. Find and report the number of different cubewords that can be constructed, modulo $ 998,244,353 $ . If one cubeword can be obtained from another by rotation or mirroring, they are considered distinct.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \leq n \leq 100,000 $ ) – the number of words. Then, $ n $ lines follow. Each of these lines contains one word that can appear on the edges of the big cube. The length of each word is between 3 and 10, inclusive. It is guaranteed that all words are different.

输出格式

Output a single integer, the number of distinct cubewords for the given list of valid words modulo $ 998,244,353 $ . Scoring Subtask 1 (21 points): the words consist only of letters 'a' - 'f' (lowercase) Subtask 2 (29 points): the words consist only of letters 'a' - 'p' (lowercase) Subtask 3 (34 points): the words consist of letters 'a' - 'p' (lowercase) and 'A' - 'P' (uppercase) Subtask 4 (16 points): the words consist of letters 'a' - 'z' (lowercase), 'A' - 'Z' (uppercase) and digits '0' - '9'

输入输出样例

输入样例 #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

说明

In the first sample, the only possibility is for the word "radar" to be on each edge of the cube. In the second sample, there are two cubes, which are just rotations of each other – the word "robot" is on every edge, and the difference between the two cubes is whether the lower left front corner contains 'r' or 't'. The third sample is similar to the second one. The fact that we can read the word on each edge in both directions does not affect the answer. In the fourth sample, there is one cube with the word "bob" on each edge. There are also $ 2^{12} = 4096 $ cubes with the word "baobab" on each edge. (For each of the 12 edges, we have two possible directions in which the word "baobab" can appear.)