G. Rotating-Calipers

G. Rotating-Calipers

G. Rotating-Calipers

时间限制:2s

空间限制:512MB

本题分数:350

题目背景

经典问题:“旋转卡壳”(一个算法的名称)有多少种读法

题目描述

现给出一个由小写字母组成的、不包含空格的文本串 \(s\) 和一个字典 \(D\) ,你需要通过以下方法解读 \(s\):

  • 将字符串进行分词,这个词必须在字典 \(D\) 中出现过;

  • 为每个词分配一种读音。

问,有多少种不同的解读方法。

当以下条件的至少一个满足时,我们认为两种解读方法不同:

  • 两种解读方法对于句子 \(s\) 的分词方法不同
  • 对于某个 \(i\),两种解读方法对第 \(i\) 个词分配的读音不同。

答案可能很大,对 \(998244353\) 取模。

输入格式

第一行一个整数\(n\),表示字典中单词的个数。

接下来 \(n\) 行每行包含一个字符串和一个整数,表示一个单词及它的读音数量。

接下来一行一个字符串 \(s\) ,是需要进行解读的句子。

输出格式

一个正整数 \(ans\),表示方案数,注意取模。

样例输入1

4 
x 2
z 3
q 2
k 2
xzqk

样例输出1

24

样例输入2

4
y 10
yy 5
ds 4
yyds 100000
yyds

样例输出2

100420

样例2解释

如果分词方法是 (y)(y)(ds),则有 \(400\) 种读法

如果分词方法是 (yy)(ds),则有 \(20\) 种读法

如果分词方法是 (yyds),则有\(100000\)种读法。

总计\(100420\)种。

样例输入3

2
aa 1000
baa 10000
aaabaa

样例输出3

0

样例3解释

无法将句子分成字典中的单词。

样例输入4

144
a 9990777
asihhugoucrozrk 578
atbuqbmqplhdcsxh 1376
b 5589273
bavxfzkoykiewmdthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucr 1273
bavxfzkoykiewmdthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoopengfcasbekjahoscizqqnpbjtkmsc 990
bhjxrcojjkdkbavxfzkoykiewmdthrffrjxqzeatbuqbmqplhdcsxhizj 1986
bthwowmue 811
c 16118386
civhyllrcjgfxkynvc 511
cojjkdkbavxfzko 291
crozrkguvkizbzhqxihacoimxdaoopengfcasbekjahosci 542
csxhizjdleddizsqpfbthwowmuebpcoovlv 1700
d 6655124
daoopengfcasbekjahoscizqqnpbjtkms 450
dckcxpnrqumpxkvipeoyorbtvgwcz 1258
dixjmibmbkwzfmftxfjepjehdckcxpnrqump 954
dixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyor 1576
dthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynr 1016
e 7045745
eatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlv 1457
ebshkyznpsnyinhcwhojr 238
ebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkgu 872
eddizsqpfbthw 1817
eoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmy 332
f 810199
fbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmib 368
fcasbekjahosciz 905
fzkoykiewmdthrffr 718
fzkoykiewmdthrffrjxqzeatbuqbmqpl 1227
g 18734918
guvkizbzhqxihaco 1773
h 3530987
hacoimxdaoopengfcasbekja 4
hdcsxhizjdleddizsqpfbthwow 966
hky 614
hrffrjxq 1945
hui 713
huiwclvzjvqlbesj 1568
hwowmuebpcoovlvuhuiwclvzjvqlbesju 859
hwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkw 26
hwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwz 1356
hyllrcjgfxkynvcumtuhcasihhugoucrozrkg 560
hyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxiha 176
hyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoop 1684
hynrhdmykwwcivhyllrcjgfxkynvcumtuhca 1224
i 3994762
ibmbkwzfmftxf 706
iewmdthrffrjxqzeatbuqbmqplhdcsxhizjd 669
ihhugoucrozrkguvkizbzhqxihacoimxdaoopen 247
ipeoyorbtvgwczv 890
ivhyllrcjg 1257
ixgqrwnijwdcyrebshkyznpsn 1647
ixjmibmbkwzfmf 1379
ixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgw 1514
izjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbe 1142
izqqnpbjtk 379
izsqpfbthwowmuebpcoovlvuhuiwcl 1593
j 8999693
jbhjxrc 97
jbhjxrcojjkdkbavxfzkoykiewmdthrffrjxqzeatbuq 809
jepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhug 1313
jxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoov 1496
jxrcojjkdkbavxfzkoykiewmdthrffrjxqzeatbuqbmqplh 254
k 2044756
kguvkizbzhqxiha 1429
kwwcivhyllrcjgfxkynvcumt 1576
kwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoopengfcas 868
kynvcumtuhcasihhugoucrozrkguvkiz 1740
l 8466011
lhdcsxhizjdled 161
llrcjgfxkynvcumt 125
lvuhuiwclvzjvqlbesjudix 1622
m 2426101
mdthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfb 193
mpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykww 1282
mt 1492
n 5999969
ngfcasbekjahoscizqqnpbj 935
nijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoope 1081
nvcumtuhcasihhugoucr 856
nvcumtuhcasihhugoucrozrkguvkizbzhqxihaco 1223
o 558853
oopeng 941
oovlvuhui 1670
opengfcasbekjahoscizqqnpbjtk 1292
ovlvuhuiwclvzjvqlbesjudixjmibmb 1378
owmuebpcoovlvuhuiwclvzjvqlbesjudixjmib 1529
owmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyre 1461
oykiewmdthr 1830
ozrkguvki 536
p 18888253
peoyorbtvgwczvixgqrwnijwdcyrebshkyznp 1962
plhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxda 879
pnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznp 1710
q 17302279
qbmqplhdcsxhizjdleddizsqpf 993
qbmqplhdcsxhizjdleddizsqpfb 231
qumpxkvipeoyorbtvgwczvixgqrwnijwd 588
qxihacoi 1425
r 1915083
rcojjkdkbavxfzkoykiewmdthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoopeng 1348
rhdmykwwcivhyllrcjgfxkynvcumtuhc 1161
rjxqzeatb 717
rkguvkizbzhq 1948
rkguvkizbzhqxihacoimxdaoo 1274
s 12688225
sxhizjdleddizsqpfbthw 1085
t 5130583
thrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyi 765
tuhcasihhugoucrozrkguvki 1015
u 2960994
ucrozrkguvki 1141
uhuiwclvzjvqlbesjudixjmibmbkwzfmftxfje 269
uiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpn 1299
umpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivh 1752
uvkizbzhqxihacoimxdaoopengfcasbekjahoscizqqnpb 1397
v 10156483
vhyllrcjgfxkynvcumtuhcasihhugoucrozrkgu 982
vuhuiwclvzjvqlbesj 1894
w 8309059
wc 1675
wclvzj 944
wdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcj 787
whojrchynrhdmy 1464
whojrchynrhdmykwwcivhyllrcjgfxkynvcumt 1310
wowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwho 1258
wzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvg 370
x 9672400
xdaoopengfcasbekjahoscizqqnpbjtkm 1257
xgqrwnijwdcyrebsh 1405
xhizjdleddizsqp 414
xih 1230
xkvipeoyorbtvgwczvixgqrwnijwdcyrebshk 955
xkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyin 947
y 12976941
yllrcjgfxkynvcu 779
ynrhdmykwwcivhyllrcjgfxkynvcumt 400
yrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyll 1246
yznpsnyinhcwhojrchynrhdmykwwcivhyllr 707
z 15356569
zhqxihacoimxdaoopengfcasbekjahoscizqqnpbjtkm 231
zjdleddizsqpfbthwowmuebpcoovl 407
zjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpn 1908
lojbhjxrcojjkdkbavxfzkoykiewmdthrffrjxqzeatbuqbmqplhdcsxhizjdleddizsqpfbthwowmuebpcoovlvuhuiwclvzjvqlbesjudixjmibmbkwzfmftxfjepjehdckcxpnrqumpxkvipeoyorbtvgwczvixgqrwnijwdcyrebshkyznpsnyinhcwhojrchynrhdmykwwcivhyllrcjgfxkynvcumtuhcasihhugoucrozrkguvkizbzhqxihacoimxdaoopengfcasbekjahoscizqqnpbjtkmscw

样例输出4

458938406

数据范围及限制

字典中的单词只包含小写字母,单词个数 \(1\le n\le 5000\)。

单词之间互不相等,即 \(i\neq j\to s_i\neq s_j\)

每个单词的解读方法数目\(1\le a_i\le 10^9\)

测试点编号 文本串长度\(\le \) 字典中单词长度之和 \(\le \) 其他约定 测试点分值
1 \(300\) \(26\) 各单词的长度均为 \(1\) 每个测试点30分
2~3 \(300\) \(5000\) 文本串仅包含一种字符 每个测试点30分
4~6 \(300\) \(5000\) 每个测试点40分
7~8 \(3000\) \(500000\) 每个测试点70分

信息

ID
1311
难度
9
分类
(无)
标签
递交数
51
已通过
4
通过率
8%
被复制
1
上传者