题目链接

传送门

题目大意

你有$n$个$m$进制的样本串,如果一个数包含其中的第$i$个,就会加上$p_i$相似度(多次包含就计算多次,包含指的是在其中连续出现),问$[L,R]$有多少数满足相似度($L,R$都是$m$进制的)。

想说的话

这套题的命名方式好像都是xxxxxx
怎么就到立华奏这里变成了豆腐?!
EXM?!

题解

这个题不要被$m$进制骗到
这个题大概就是跑一个字符串匹配问题嘛
然后要求匹配成功的次数少于某一个特定的值
首先进行字符串匹配我们想到了AC自动机这个东西
然后我们把平时的$end$节点换一下 这次不是代表这个单词结束了 而变成这个单词所能获得的价值
这样我们的AC自动机就建好了
然后考虑到这个题问的是一个区间$[L,R]$所以我们拆成两个问题来考虑$[1,L-1],[1,R]$
这样的话我们大概可以在上面跑一个数位$dp$?
转移的时候我们利用AC自动机的转移边来进行转移
状态方程直接看代码吧
这里我的$dp[i][j][k][0/1][0/1]$代表当前这个数匹配到了第$i$位,在AC自动机上面的第$j$个节点,当前的匹配值是$k$,后面两个值分别代表有无前导零和是否压上界
这样的话转移一下就行了

代码