Subsequences Galore
Contest: Educational Codeforces Round 119 (Rated for Div. 2)
Difficulty rating: 2400
Tags: bitmasks, combinatorics, dp

For a sequence of strings $$$[t_1, t_2, \dots, t_m]$$$, let's define the function $$$f([t_1, t_2, \dots, t_m])$$$ as the number of different strings (including the empty string) that are subsequences of at least one string $$$t_i$$$. $$$f([]) = 0$$$ (i. e. the number of such strings for an empty sequence is $$$0$$$).

You are given a sequence of strings $$$[s_1, s_2, \dots, s_n]$$$. Every string in this sequence consists of lowercase Latin letters and is sorted (i. e., each string begins with several (maybe zero) characters a, then several (maybe zero) characters b, ..., ends with several (maybe zero) characters z).

For each of $$$2^n$$$ subsequences of $$$[s_1, s_2, \dots, s_n]$$$, calculate the value of the function $$$f$$$ modulo $$$998244353$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 23$$$) — the number of strings.

Then $$$n$$$ lines follow. The $$$i$$$-th line contains the string $$$s_i$$$ ($$$1 \le |s_i| \le 2 \cdot 10^4$$$), consisting of lowercase Latin letters. Each string $$$s_i$$$ is sorted.

Output format:
Since printing up to $$$2^{23}$$$ integers would be really slow, you should do the following:

For each of the $$$2^n$$$ subsequences (which we denote as $$$[s_{i_1}, s_{i_2}, \dots, s_{i_k}]$$$), calculate $$$f([s_{i_1}, s_{i_2}, \dots, s_{i_k}])$$$, take it modulo $$$998244353$$$, then multiply it by $$$k \cdot (i_1 + i_2 + \dots + i_k)$$$. Print the XOR of all $$$2^n$$$ integers you get.

The indices $$$i_1, i_2, \dots, i_k$$$ in the description of each subsequences are $$$1$$$-indexed (i. e. are from $$$1$$$ to $$$n$$$).

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

Example input:
3
a
b
c

Example output:
92

Example input:
2
aa
a

Example output:
21

Editorial:
For a string $$$t$$$, let's define its characteristic mask as the mask of $$$n$$$ bits, where $$$i$$$-th bit is $$$1$$$ if and only if $$$t$$$ is a subsequence of $$$s_i$$$. Let's suppose we somehow calculate the number of strings for each characteristic mask, and we denote this as $$$G(x)$$$ for a mask $$$x$$$. How can we use this information to find $$$f([s_{i_1}, s_{i_2}, \dots, s_{i_k}])$$$? Suppose this set of strings is represented by a mask $$$x$$$, then the strings which are not included in $$$f$$$ are the strings such that their characteristic mask has bitwise AND with $$$x$$$ equal to $$$0$$$, i. e. these characteristic masks are submasks of $$$2^n - 1 \oplus x$$$. We can use SOS DP to calculate these sums of $$$G(x)$$$ over submasks in $$$O(2^n n)$$$.
The only problem is how to calculate $$$G(x)$$$ for every mask. Let's analyze when a string is a subsequence of a sorted string $$$s_i$$$. The subsequence should be sorted as well, and the number of occurrences of every character in a subsequence should not exceed the number of occurrences of that character in $$$s_i$$$. So, if there are $$$c_1$$$ characters a in $$$s_i$$$, $$$c_2$$$ characters b in $$$s_i$$$, and so on, then the number of its subsequences is $$$\prod \limits_{j=1}^{26} (1 + c_j)$$$.
What about subsequences of every string from a set? These conditions on the number of occurrences should apply to every string in the set, so, for each character, we can calculate the minimum number of occurrences of this character in each string of the set, add $$$1$$$, and multiply these numbers to get the number of strings that are subsequences of each string in a set.
These values can be calculated in $$$O(2^n (n + A))$$$ for all $$$2^n$$$ subsequences of $$$[s_1, s_2, \dots, s_n]$$$ using recursive approach. Can these numbers be used as $$$G(x)$$$? Not so fast. Unfortunately, these values (let's call them $$$H(x)$$$) are the numbers of subsequences of the chosen sets of strings, but we have no information about the strings that are not included in the chosen set of strings. To handle it, we can use the following equation: $$$H(x) = \sum \limits_{x \subseteq y} G(y)$$$, where $$$x \subseteq y$$$ means that $$$x$$$ is a submask of $$$y$$$. To transform the values of $$$H(x)$$$ into the values of $$$G(x)$$$, we can flip all bits in the masks (so $$$H(x)$$$ is the sum of $$$G(y)$$$ over all submasks of $$$x$$$), apply inverse SOS DP (also known as Mobius transformation), and then flip all bits in the masks again. So, we found a way to calculate all values of $$$G(x)$$$ in $$$O(2^n (n + A))$$$, and we have already discussed what to do with them in the first paragraph of the editorial.
The overall complexity of the solution is $$$O(2^n (n+A))$$$.