D-Kendieer 的 LCP 问题_牛客挑战赛87

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定 $n$ 个字符串 $s_1, s_2, \dots, s_n$ 。现在有 $q$ 次查询，每次查询给出 $k$ 个不同的索引 ${\rm idx}_1, {\rm idx}_2, \dots, {\rm idx}_k\left(1\leq {\rm idx}_j\leq n\right)$ ，这 $k$ 个索引构成的集合 $\Bbb S$ 共有 $2^k - 1$ 个非空子集 $^\texttt{[1]}$ 。
$\hspace{15pt}$ 对于集合 $\Bbb S$ 的每一个非空子集 $\Bbb T = \{{\rm idx'}_1, {\rm idx'}_2, \dots, {\rm idx'}_{|\Bbb T|}\}$ ，定义其贡献为该子集中所有索引对应的字符串的最长公共前缀 $^\texttt{[2]}$ （Longest Common Prefix, LCP）的长度，即： $\left|\operatorname{LCP}(s_{{\rm idx'}_1},s_{{\rm idx'}_2},\dots,s_{{\rm idx'}_{|\Bbb T|}})\right|$ ，简记为 $f(\Bbb T)$ 。

$\hspace{15pt}$ 请对于每次查询，计算所有 $2^k - 1$ 个非空子集的 LCP 长度之和。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。即：

$\displaystyle\left(\sum_{\emptyset \neq \Bbb T \subseteq \Bbb S} f(\Bbb T) \right)\bmod 998\,244\,353$

【名词解释】
$\hspace{15pt}$ 非空子集 $^\texttt{[1]}$ ：对于给定集合 $\Bbb S$ ，如果一个集合 $\Bbb A$ 满足：至少包含一个元素，且 $\Bbb A$ 中的所有元素都属于集合 $\Bbb S$ ，则称 $\Bbb A$ 为 $\Bbb S$ 的非空子集。
$\hspace{15pt}$ 最长公共前缀 $^\texttt{[2]}$ （lcp）：对于一个或多个字符串，从它们的第一个字符开始，向后连续取若干个字符，使得取出的这些字符串完全相同，长度最长的那一段字符串称为这些字符串的最长公共前缀。特别地，最长公共前缀可以为空串。例如：
$\hspace{23pt}\bullet\,$ $\operatorname{LCP}(\texttt{$ ；
$\hspace{23pt}\bullet\,$ $\operatorname{LCP}(\texttt{$ ；
$\hspace{23pt}\bullet\,$ $\operatorname{LCP}(\texttt{$ ；
$\hspace{23pt}\bullet\,$ $\operatorname{LCP}(\texttt{$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入两个整数 ，表示字符串的数量、查询的次数。
此后  行，第  行输入一个长度为 ，由小写英文字母组成的字符串 。
此后  行，第  行先输入一个整数 ，表示第  次查询的索引数量，随后在同一行输入  个互不相同的整数 ，表示该查询涉及的字符串编号。

除此之外，保证单个测试文件的  之和、 之和均不超过 ， 之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出  个整数，第  个整数表示第  次查询的所有非空子集的 LCP 长度之和对  取模后的结果。

示例1

输入

复制

1
5 3
abaac
abcac
abbac
abbbc
acbb
3 1 2 3
2 3 4
3 3 2 5

输出

复制

23 13 19

说明

对于第一次查询，字符串集合为 ，对应字符串为 、、，全部非空子集：
，贡献 ；
，贡献 ；
，贡献 ；
，贡献 ；
，贡献 ；
，贡献 ；
，贡献 。
因此，所有非空子集的 LCP 长度之和为 。

对于第三次查询，字符串集合为 ，对应字符串为 、、，全部非空子集：
，贡献 ；
，贡献 ；
，贡献 ；
，贡献 ；
，贡献 ；
，贡献 ；
，贡献 。
因此，所有非空子集的 LCP 长度之和为 。

示例2

输入

复制

3
4 1
abacaba
abac
abaccb
ab
4 1 2 3 4
7 6
abacaba
abacabcde
abacacc
abababa
abababxyz
abcdeabc
aaaaaaa
2 1 2
2 1 4
3 1 2 3
3 4 5 6
2 6 7
4 1 2 4 5
7 5
cirnobaka
bakaderer
bakadieer
flyingbaka
cxbaka
bakapoo
cirnobaka
3 1 2 5
4 2 3 4 5
2 1 7
5 3 2 5 7 6
3 1 4 5

输出

复制

49
22 17 44 36 16 71
25 39 27 58 26