「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}\)代表\(i\sim 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\n",ans);

	return 0;

}

---

2019.2.21