Type: Default 1000ms 256MiB

这里怎么全是阿蒙

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

克莱恩收到了一份秘密聚会的来宾名单。为了隐藏身份,每位来宾都使用一个仅由小写英文字母组成的代号。

名单背面写着一条警告:

代号的开头越相似,来宾就越有可能是同一个人的分身。

克莱恩决定展开调查。

第一位来宾戴上了单片眼镜。

第二位来宾也戴上了单片眼镜。

负责调查的工作人员看了看他们,同样戴上了单片眼镜。

“既然大家都到了,”其中一位来宾说,“不如查查谁最像阿蒙。”

Description

共有 nn 位来宾,第 ii 位来宾的代号为 sis_i。不同来宾可以使用相同的代号。

两位来宾的“可疑值”定义为他们代号的最长公共前缀长度:从第一个字符开始依次比较,直到出现不同字符或其中一个字符串结束,之前连续相同的字符数量就是可疑值。

例如,amon 与 amog 的可疑值为 33,am 与 amon 的可疑值为 22,amon 与 klein 的可疑值为 00。

每位来宾都要检查全部 nn 位来宾,包括自己。因此一共进行 n2n^2 次检查。第 ii 位检查第 jj 位与第 jj 位检查第 ii 位分别计数;检查自己时,可疑值等于自己的代号长度。

请计算所有检查的可疑值之和,对 998244353998244353 取模。即计算:

$$\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\operatorname{LCP}(s_i,s_j)\right)\bmod 998244353.$$

“为什么连自己也要查?”

“为了保证调查公正。”阿蒙扶了扶单片眼镜,在自己的名字旁写下了“非常可疑”。

Format

Input

第一行一个整数 nn,表示来宾数量。

接下来 nn 行,每行一个非空字符串 sis_i,表示第 ii 位来宾的代号。

保证 1≤n≤1061\le n\le 10^6,字符串仅包含小写英文字母,且所有字符串的长度之和不超过 10610^6。

Output

输出一个整数,表示所有检查的可疑值之和对 998244353998244353 取模的结果。

Samples

3
am
amon
amog
24

Explanation

三位来宾分别进行检查,得到的可疑值如下:

调查员的代号 检查 am 检查 amon 检查 amog
am 2 2
amon 4 3
amog 3 4

总和为 2424。每个人都很可疑,尤其是他们自己。

Limitation

时间限制:每个测试点 11 秒。

空间限制:每个测试点 512512 MiB。

(建议先去了解Trie树后再去做这道题)

验题

Not Attended
Status
Done
Rule
XCPC
Problem
18
Start at
2026-9-16 19:00
End at
2026-9-26 19:00
Duration
240 hour(s)
Host
Partic.
12