#P2020095. 密信与计数

密信与计数

密信与计数

题目描述

背景

小明和小鱼研究出了一套加密通信的规则。小鱼给小明发送信息(仅由小写字母组成的字符串)的流程如下:

小鱼使用手中的密码本,将明文信息生成密文,该密文也仅由小写字母组成且与明文等长;

小鱼将密文发送给小明;

小明使用手中的密码本(内容与小鱼的密码本很可能不同),将密文解密为明文,该明文与小鱼的原信息一定是相同的。

解密密码本

虽然你不知道小鱼是如何加密的,但是你拿到了小明用来解密的密码本。

小明的密码本共有n页(从 1 到n编号)。每页有 26 行,对应着字母a到z。每行写有一个小写字母out和一个整数next(1≤next≤n)。对于每一页,其上面的 26 个out是两两不同的。

小明在解密信息时,先将密码本翻到第 1 页,然后对于密文的每一个字符依次进行以下操作:在当前页找到该字符对应的行,在纸上写下该行的out字符,并将密码本翻到第next页。扫描完密文的每个字符后,纸上写下的字符就依次形成了明文。

下面是一个密码本的例子:

            Page 1              Page 2
'a'    (out='x',next=1)    (out='w',next=2)
'b'    (out='y',next=2)    (out='z',next=1)
'c'    (out='z',next=2)    (out='y',next=2)
'd'         ......              ......
...         ......              ......
'z'         ......              ......

None

在这个例子下,如果小明收到的密文为abac,则相应的解密过程如下:

初始时,将密码本翻到第 1 页;

遇到密文字符a,查到out为x,next为 1,则向纸上写字符x,密码本仍在第 1 页;

遇到密文字符b,查到out为y,next为 2,则向纸上写字符y,将密码本翻到第 2 页;

遇到密文字符a,查到out为w,next为 2,则向纸上写字符w,密码本仍在第 2 页;

遇到密文字符c,查到out为y,next为 2,则向纸上写字符y,密码本仍在第 2 页。

所以,解密得到的明文为xywy。

词典

你还拿到了一个词典,小鱼和小明的通信内容明文都是由这个词典中的字符串拼接而成的。词典中不会有空串,不会有两个完全相同的单词,也不会存在某个单词是另一个单词的前缀。

例如,词典有 4 个单词:

dog
is
good
happy

None

那么dogishappy、happydogisgooddog都是可能出现的通信内容,但是dogood、hisappy是不合法的明文。

此外,小鱼在编写明文时,会特别注意使它对应的密文“看起来像密文”。“看起来像密文”是指,对应的密文当中不应当包含词典中的任何词作为子串。例如明文doggood本身符合词典的要求,但假设它对应的密文是xisxxyz,由于其中包含了is为子串,则小鱼也不会编写doggood这一明文。

本题的任务

给定小明的解密密码本和词典,我们定义k-合法密文是指:

长度为k,仅包含小写字母的字符串;

不包含词典中的任何一个串为子串;

其对应的明文可以通过词典中的字符串拼接而成。

除了密码本和词典以外,我们还输入正整数m。你需要对于k=1,2,3,…,m输出k-合法密文的数量。由于答案可能很大,每个数只需要对 998244353 取模后输出即可。

输入格式

第一行输入两个正整数n,m。

接下来输入小明的解密密码本。密码本包含 26 行,每行有n个元素。其中第i行第j列的元素输入密码本第j页第i行的内容。每个元素先输入out,后输入next。例如输入y2表示out为y,next为 2。注意字母和数字之间没有空格。

接下来输入词典,词典的每个单词占据一行。

输出格式

输出m行,每行一个整数,依次表示k=1,k=2,…,k=m时,k-合法密文的数量,对 998244353 取模的结果。

数据范围

(原站未提供,导入后需人工补齐)

样例

2 4
x2 w2
y2 z1
z1 y2
a2 x1
b2 a2
c1 b1
d2 c2
e2 d1
f1 e2
g2 f1
h2 g2
i1 h1
j2 i2
k2 j1
l1 k2
m2 l1
n2 m2
o1 n1
p2 o2
q2 p1
r1 q2
s2 r2
t2 s1
u1 t2
v2 u1
w2 v2
a
de
hh
1
2
3
5
1 30
n1
b1
k1
w1
l1
q1
r1
y1
h1
o1
f1
d1
u1
i1
g1
p1
c1
m1
v1
x1
j1
t1
z1
e1
s1
a1
yyyyy
a
sss
ffff
uuuu
n
rrrrr
zzzz
dd
l
w
x
jjj
i
tttt
kkk
ee
ggg
qq
4
15
62
254
1037
4238
17318
70762
289147
1181515
4827896
19727703
80611180
329392745
347717570
508636782
512101020
990699955
897183687
992683554
367164478
441771655
282208579
707622895
680435638
349679885
49272719
821317456
174000209
371253693

提示

样例1说明

![RequireFile.png](file://4822116c33.png)

样例2说明

该样例的输入文件与第 18 个测试点仅有m不同(详见下述)。

评测用例规模与约定

本题共 25 个测试点,每个 4 分。

对于所有的测试点,1≤n≤50,1≤m≤1000,词典不为空且所有单词的长度之和不超过 50。

对于编号为偶数的测试点,n=1。

其他的特殊性质如下表所述:

![RequireFile (1).png](file://1d40f3c4e0.png)