← 返回题目列表

Codeforces · 1620/G

G. 大量子序列

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

对于字符串序列 $$$[t_1, t_2, \dots, t_m]$$$,我们将函数 $$$f([t_1, t_2, \dots, t_m])$$$ 定义为至少一个字符串 $$$t_i$$$ 的子序列的不同字符串(包括空字符串)的数量。 $$$f([]) = 0$$$ (即空序列中此类字符串的数量为 $$$0$$$)。

给定一个字符串序列 $$$[s_1, s_2, \dots, s_n]$$$。该序列中的每个字符串都由小写拉丁字母组成,并且经过排序(即,每个字符串以几个(可能为零)字符 a 开头,然后是几个(可能为零)字符 b,...,以几个(可能零)字符 z 结尾)。

对于 $$$[s_1, s_2, \dots, s_n]$$$ 的每个 $$$2^n$$$ 子序列,计算函数 $$$f$$$ 模 $$$998244353$$$ 的值。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 23$$$) — 字符串的数量。

然后是 $$$n$$$ 行。第 $$$i$$$ 行包含字符串 $$$s_i$$$ ($$$1 \le |s_i| \le 2 \cdot 10^4$$$),由小写拉丁字母组成。每个字符串 $$$s_i$$$ 均已排序。

输出

由于打印最多 $$$2^{23}$$$ 整数会非常慢,因此您应该执行以下操作:

对于每个 $$$2^n$$$ 子序列(我们表示为 $$$[s_{i_1}, s_{i_2}, \dots, s_{i_k}]$$$),计算 $$$f([s_{i_1}, s_{i_2}, \dots, s_{i_k}])$$$,接受它对 $$$998244353$$$ 取模,然后乘以 $$$k \cdot (i_1 + i_2 + \dots + i_k)$$$。打印得到的所有 $$$2^n$$$ 整数的 XOR。

每个子序列描述中的索引 $$$i_1, i_2, \dots, i_k$$$ 是 $$$1$$$ 索引的(即从 $$$1$$$ 到 $$$n$$$)。

示例

输入 #1

3
a
b
c

输出 #1

92

输入 #2

2
aa
a

输出 #2

21

输入 #3

2
a
a

输出 #3

10

输入#4

2
abcd
aabb

输出#4

124

输入 #5

3
ddd
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaabbbbbbbbbbbcccccccccccciiiiiiiiiiiiiiiiiiiiiiooooooooooqqqqqqqqqqqqqqqqqqvvvvvzzzzzzzzzzzz

输出 #5

15706243380