#PQJ767x6197. QOJ 767_6197

    ID: 3038 传统题 3000ms 2048MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2020-2021 集训队互测字符串后缀数组

QOJ 767_6197

标题: 太阳神的宴会 - Problem - QOJ.ac

#6197. 太阳神的宴会

Statistics

The problem was used in the following contests:

This problem is prepared by nealchen .

太阳神为了体察凡间人情,化名 EntropyIncreaser💫 下凡。EntropyIncreaser💫,也就是 EI,合起来写就是日,意思是太阳神。

今天,EntropyIncreaser💫 召集了粉丝群里的 n 名群员来参与他的盛宴。宴会上,他和群员们玩起了益智游戏,以展示自己无量的智慧。

游戏的一方是 EntropyIncreaser💫;另一方是 n 名群员,他们排成了一行,依次编号为 1,2,…,n。字符集是前 k 个英文字母集合 Σ,也就是说,游戏中所有字符串均由 Σ 的元素构成。

游戏一开始,EntropyIncreaser💫 给每个群员都发了一个字符串,第 i 个群员的字符串是 Si。随后,每个群员都任意地从收到的字符串 Si 中挑选一个子串 Ti(子串必须连续,但可以为空串)。群员们把各自所挑选的子串 Ti 输入打字机,它们按照顺序没有间隔地接成了一个完整的字符串 T=T1T2⋯Tn。EntropyIncreaser💫 只能知道 T,而不知道每个字符是哪位群员输入的。游戏的规则是,只要解出一组可能的 T1,T2,…,Tn,就能获得胜利。

EntropyIncreaser💫 看到字符串 T,不假思索,将它划分成 n 个字符串 T1′T2′⋯Tn′(同样可以为空)。群员们惊奇地发现,Ti′ 确实是他们所收到的串 Si 的子串!

EntropyIncreaser💫 笑笑:『这是一道大水题,没什么难的。我们来加大一点儿难度。』

这时月亮女神玲雨提出了游戏的加强版。

现在第 i 位群员仍然取出了子串 Ti。在每位群员输入前,键盘的键位都会被秘密打乱,而群员仍然照常输入,也就是每位群员现在分配了一个 Σ 上的置换 fi,Ti 的第 j 个字符 Tij 输入时将变成 fi(Tij),所有输入的字符连接起来构成了 T。EntropyIncreaser💫 的目标仍然是解出一组可能的 T1,T2,…,Tn。

EntropyIncreaser💫 仔细端详,再次将 T 分成了 n 个字符串 T1′,T2′,…,Tn′,群员们沸腾了:确实存在置换 fi,使得 Si 的一个子串经过 fi 的作用得到 Ti′!

宴会从清晨进行到夜晚。在宴会的尾声,EntropyIncreaser💫 宣布:『神将赐予群友数学的智慧,但是要先经过三道考验。』

现在,来自计数之神大加强的第一道考验摆在了你面前——请你来数一数,在最后一个游戏中,有多少个字符串 T 有至少一组解?答案可能很大,所以对 998244353 取模。

输入格式

第一行两个正整数 n,k。

接下来 n 行,每行一个字符串,依次表示 S1,S2,…,Sn。

输出格式

输出有解的字符串的数量,对 998244353 取模。

样例一

input

2 2
aa
a

output

11

explanation

用 ϵ 指代空串。

S1 的子串有 ϵ, a, aa,打乱键位后可获得 ϵ, a, b, aa, bb。

S2 的子串有 ϵ, a,打乱键位后可获得 ϵ, a, b。

连接起来,有解的串有:ϵ, a, b, aa, ab, ba, bb, aaa, aab, bba, bbb。

样例二

input

2 2
aa
ab

output

17

限制与约定

简记 L=∑i=1n|Si|。

保证 2≤k≤26,Si 非空,L≤106。

子任务一(2分):n=1,k=2,L≤1000。

子任务二(7分):n=1,L≤1000。

子任务三(11分):n=1,L≤105。

子任务四(13分):k=2,L≤1000。

子任务五(17分):L≤1000。

子任务六(31分):k≤5。

子任务七(19分):无特殊限制。