[BZOJ3530/Luogu3311][SDOI2014]数数(AC自动机,数位动态规划)

发布于 2018-03-24  3 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3530/Luogu3311][SDOI2014]数数(AC自动机,数位动态规划)

Description

我们称一个正整数N是幸运数,当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22,333,0233)时,233是幸运数,2333、20233、3223不是幸运数。
给定N和S,计算不大于N的幸运数个数

Tag

AC自动机,数位动态规划

解决思路

把数字串插入到AC自动机中,那么首先我们知道,在匹配构造的时候,是不能走到单词结尾的地方的。
然后我们先算位数小于 N 的位数的方案数。设 F[i][j] 表示构造到第 i 位当前在 AC 自动机的第 j 号点的方案数,那么向它的所有不是数字串结尾的儿子转移即可。
再考虑位数严格等于 N 的方案数,那么类似数位 DP 里的做法,设F[i][j][0/1] 其中 [0] 表示严格小于,[1] 表示严格等于的方案数。那么转移的时候严格等于的就只枚举到对应的 N 中的那一位转移,而小于的则可以在整个字符集中转移,分别讨论一下。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3530/Luogu3311][SDOI2014]数数(AC自动机,数位动态规划)


HNCJ OIer 一枚