「SDOI2014」数数解题报告

「SDOI2014」数数

题目描述

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

给定 (N) 和 (S)，计算不大于 (N) 的幸运数个数。

输入格式

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

输出格式

输出一行一个整数，表示答案模 (10^9+7) 的值。

数据范围与提示

我们以 (l) 表示 (N) 的长度，(L) 表示 (S) 中所有串长度之和。
对于所有数据，(1 leq l leq 1200 , 1 leq M leq 100 , 1 leq L leq 1500)。

关于多子串的东西可以想到AC自动机，可以在上面dp。

(dp_{i,j,0/1})代表(isim n)位数字目前在AC自动机上匹配到节点(j)是否有最高位限制。

最后一位可以像数位dp那样非常简单的转移，有个坑点是(S)中有前导(0)，但是(N)中没有。

有一种简单的处理方法是在建完AC自动机后把边(ch[root][0])删掉

Code:

#include <cstdio>
#include <cstring>
const int mod=1e9+7;
const int N=1520;
inline void add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
char s[N],t[N];
int ch[N][10],endro[N],fail[N],tot,q[N],l=1,r,bit[N],dp[N][N][2];
void ins()
{
	scanf("%s",s+1);
	int n=strlen(s+1),now=0;
	for(int i=1;i<=n;i++)
	{
		if(!ch[now][s[i]-'0']) ch[now][s[i]-'0']=++tot;
		now=ch[now][s[i]-'0'];
	}
	endro[now]=1;
}
void build()
{
	for(int i=0;i<10;i++)
		if(ch[0][i])
			q[++r]=ch[0][i];
	while(l<=r)
	{
		int now=q[l++];
		for(int i=0;i<10;i++)
		{
			if(ch[now][i]) fail[q[++r]=ch[now][i]]=ch[fail[now]][i];
			else ch[now][i]=ch[fail[now]][i];
		}
	}
	ch[0][0]=0;
}
int main()
{
	scanf("%s",t+1);
	int n=strlen(t+1),m;
	for(int i=1;i<=n;i++) bit[i]=t[n+1-i]-'0';
	scanf("%d",&m);
	for(int i=1;i<=m;i++) ins();
	build();
	dp[n+1][0][1]=1;
	for(int i=n+1;i>1;i--)
		for(int j=0;j<=tot;j++)
			for(int l=0;l<=1;l++)
				for(int k=0,u=l?bit[i-1]:9;k<=u;k++)
				{
					int to=ch[j][k];
					if(!endro[to]) add(dp[i-1][to][l&k==bit[i-1]],dp[i][j][l]);
				}
	int ans=mod-1;
	for(int i=0;i<=tot;i++) add(ans,dp[1][i][0]),add(ans,dp[1][i][1]);
	printf("%d
",ans);
	return 0;
}