#PQJ767x6197. QOJ 767_6197
QOJ 767_6197
标题: 太阳神的宴会 - Problem - QOJ.ac
#6197. 太阳神的宴会
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分):无特殊限制。