BZOJ3530:[SDOI2014]数数(AC自动机,数位DP)

Description

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

Input

输入的第一行包含整数N。
接下来一行一个整数M,表示S中元素的数量。
接下来M行,每行一个数字串,表示S中的一个元素。

Output

输出一行一个整数,表示答案模109+7的值。

Sample Input

20
3
2
3
14

Sample Output

14

HINT

下表中l表示N的长度,L表示S中所有串长度之和。

1 < =l < =1200 , 1 < =M < =100 ,1 < =L < =1500

Solution

一个挺简单的一个题……建出来$AC$自动机然后在上面直接跑数位$DP$就好了。只不过有点小地方需要注意。

用$DFS(zero,lim,pos,now)$是否有前导0,是否卡上界,第$pos$位,自动机上第$now$个点。

为什么要存前导0呢?我们可以发现有这么一个例子:

10

1

01

这个跑出来应该是10,然而不记前导零特判一下会跑出来9。这是因为当幸运串为01的时候我们会忽略前导0,所以是合法的。

只需要在$DFS$的时候特判一下,如果有前导0,且幸运数这一位选0,且$now$还在根节点,就让$now$停在根节点就好了。

建立AC自动机的时候,如果某个节点能够沿着fail指针跳到单词节点,那么这个节点也应当禁止通过……

自测一时爽

Code

 #include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define N (1509)
#define MOD (1000000007)
using namespace std; int sz,Son[N][],Fail[N],End[N];
int cnt,m,x,f[N][N],a[N],spc[N];
char n[N],s[N];
queue<int>q; void Insert(char s[])
{
int now=;
for (int i=,l=strlen(s); i<l; ++i)
{
int c=s[i]-'';
if (!Son[now][c]) Son[now][c]=++sz;
now=Son[now][c];
}
End[now]++;
} void Build_Fail()
{
for (int i=; i<=; ++i)
if (Son[][i]) q.push(Son[][i]);
while (!q.empty())
{
int now=q.front(); q.pop();
for (int i=; i<=; ++i)
{
if (!Son[now][i])
{
Son[now][i]=Son[Fail[now]][i];
continue;
}
Fail[Son[now][i]]=Son[Fail[now]][i];
q.push(Son[now][i]);
}
}
} int DFS(int zero,int lim,int pos,int now)
{
if (pos==) return ;
if (!zero && !lim && f[pos][now]!=-) return f[pos][now];
f[pos][now]=;
int up=lim?n[pos]-'':;
for (int i=; i<=up; ++i)
if (!End[Son[now][i]])
{
if (zero && !i && !now) (f[pos][now]+=DFS(zero,lim&&==up,pos-,))%=MOD;
else
{
int flag=,t=Son[now][i];
while (t)
{
if (End[t]) {flag=; break;}
t=Fail[t];
}
if (!flag) continue;
(f[pos][now]+=DFS(zero&&!i,lim&&i==up,pos-,Son[now][i]))%=MOD;
}
}
return f[pos][now];
} int main()
{
memset(f,-,sizeof(f));
scanf("%s%d",n+,&m); cnt=strlen(n+);
for (int i=; i<=m; ++i)
scanf("%s",s),Insert(s);
Build_Fail();
for (int i=,j=cnt; i<j; ++i,--j)
swap(n[i],n[j]);
printf("%d\n",DFS(,,cnt,)-);
}
上一篇:Common Subsequence(最长公共子序列)


下一篇:JAVA基础——包机制