Cubeword
Contest: CEOI 2019 day 1 online mirror (unrated, IOI format)
Tags: *special, brute force, dp, meet-in-the-middle

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.

Input format:
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 format:
Output a single integer, the number of distinct cubewords for the given list of valid words modulo $$$998,244,353$$$.

Constraints:
Time limit: 1.7 s
Memory limit: 1024.0 MB

Note:
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'

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.)

Example input:
1
radar

Example output:
1

Example input:
1
robot

Example output:
2

Editorial:
In all subtasks we solve the problem independently for each possible length of a word and sum the answers.
To handle palindromes and words that are reverse of each other, we first add the reverse of each word to the dictionary and then remove duplicates. Then, we will fix a direction for each edge and we will ask that the word written along the edge in that direction has to be in the new wordlist. (This is clearly equivalent to the original problem, and it allows us to choose the directions of edges in any way that suits our approach.)
For each pair of letters $$$a$$$, $$$b$$$ precompute the number of words that begin with $$$a$$$ and end in $$$b$$$.
Subtask 1
We brute-force all combinations of letters in the vertices of the cube and use the precomputed values to find how many cubewords are there with these letters fixed. Complexity $$$\mathcal O(n + |\Sigma|^8)$$$.
Subtask 2
Label the vertices $$$1$$$ through $$$8$$$ with vertices $$$1$$$ through $$$4$$$ lying around the bottom face and vertex $$$i+4$$$ directly above vertex i. We will assign letters to vertices in the increasing order of their ids. Start by assigning letters to vertices $$$1$$$ through $$$4$$$ and count the number of possibilities of assigning letters to the edges on the bottom face. We then try all possibilities of assigning a letter to vertex $$$5$$$, and account for the edge $$$\{1,5\}$$$. Note that all edges incident to the vertex $$$1$$$ are already processed, hence we may now drop the value of $$$1$$$ from our state. More generally, after processing vertex $$$j$$$ we can forget the letter in vertex $$$j-4$$$.
This forms a dynamic programming solution with $$$8 \cdot |\Sigma|^4$$$ states, where each state has $$$|\Sigma|$$$ transitions, each of which can be performed in constant time.
Complexity $$$\mathcal O(n + |\Sigma|^5)$$$.
Subtask 3
When viewed as a graph, the cube is bipartite with both partitions of size $$$4$$$. Consider all possibilities of assigning the letters to one partition. We want to process each of the remaining vertices in $$$\mathcal O(1)$$$.
Precompute $$$D[a][b][c]$$$ as the number of triples of words such that they all begin with the same letter and the other end with $$$a$$$,$$$b$$$,$$$c$$$, respectively. This precomputation can be done naively in $$$\mathcal O(|\Sigma|^4)$$$.
Coming back to our problem, let the letters on one partition be $$$a$$$,$$$b$$$,$$$c$$$,$$$d$$$ respectively. Observe that the answer is $$$D[a][b][c] \cdot D[a][b][d] \cdot D[a][c][d] \cdot D[b][c][d]$$$.
Total complexity is $$$\mathcal O(n + |\Sigma|^4)$$$.
Fun fact: Geometrically, this solution can be viewed as follows. A cube can be cut into five tetrahedrons: one that's completely inside and four such that each of them contains one corner of the cube (and thus three edges). In this solution you brute force the letters in the corners of the inner tetrahedron, and once you fix those, each of the remaining tetrahedrons is independent of the other three.
Subtask 4
To reduce the complexity even further, note that a cube can be rotated and flipped in $$$48$$$ different ways: there are $$$6$$$ possibilities for the bottom face, after the bottom face is fixed, there are $$$4$$$ options for the front face, and after that there are two possibilities on the left face. In exactly half of the rotations, the vertex partitions swap places (for instance when rotating the cube by 90 degrees in any principal axis) and in the second half they stay in position, possibly permuting the vertices (for example rotation the cube by 180 degrees, or rotating the cube by 90 degrees and then mirroring it).
Assume for a moment that the letters $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ on the vertices of the first partition are guaranteed to be distinct. Then there is a way of rotating and flipping the cube in such a way that $$$a < b < c < d$$$. Hence we can calculate the answer only for this case and multiply it by $$$24$$$.
However, the letters $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ are not necessarily distinct. To mitigate this, we simply consider all possibilities of the form $$$a \leq b \leq c \leq d$$$, and multiply the answer of each of them by the number of permutations of $$$(a,b,c,d)$$$. This reduces this step of the solution to $$$\mathcal O(|\Sigma|^4 / 24)$$$.
Precomputing the array $$$D$$$ can also be optimised – we again consider only cases $$$a \leq b \leq c$$$ and use the fact that $$$D[a][b][c] = D[a][c][b] = \ldots = D[c][b][a]$$$. The complexity of this step is thus reduced to $$$\mathcal O(|\Sigma|^4 / 6)$$$.
To summarise, we are able to reduce the complexity $$$6$$$-fold by considering symmetries.