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

样例输入2

4
y 10
yy 5
ds 4
yyds 100000
yyds

样例输出2

样例2解释

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

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

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

总计 $100420$ 种。

样例输入3

2
aa 1000
baa 10000
aaabaa

样例输出3

样例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

难度

分类

(无)

标签

2021小兰赛

递交数

已通过

通过率

被复制

上传者

Takagi-san (njnu19200437)

在下列比赛中:

2021年互联网创新创业科技节程序设计大赛

G. Rotating-Calipers

G. Rotating-Calipers

G. Rotating-Calipers

题目背景

题目描述

输入格式

输出格式

样例输入1

样例输出1

样例输入2

样例输出2

样例2解释

样例输入3

样例输出3

样例3解释

样例输入4

样例输出4

数据范围及限制

信息

相关

状态

开发

支持

G. Rotating-Calipers

G. Rotating-Calipers

G. Rotating-Calipers

题目背景

题目描述

输入格式

输出格式

样例输入1

样例输出1

样例输入2

样例输出2

样例2解释

样例输入3

样例输出3

样例3解释

样例输入4

样例输出4

数据范围及限制

信息

相关

状态

开发

支持

还没有账户？

登录