Accepted/15516 kb/884 ms

bzoj3530.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct TrieNode{
	int flag,fail,next[10];
}T[1505];
int f[1205][1505][2];
int root=1;
int tT=1;
const int mod=1000000007;
void trieInsert(char *numb)
{
	int len=strlen(numb);
	int p=root;
	for (int i=0;i<len;i++)
	{
		if (T[p].next[numb[i]-'0']==0)
			T[p].next[numb[i]-'0']=++tT;
		p=T[p].next[numb[i]-'0'];
	}
	T[p].flag=true;
}
void trieBuild()
{
	int u,v;
	queue<int>Q;
	T[root].fail=0;
	Q.push(root);
	while (!Q.empty())
	{
		u=Q.front();Q.pop();
		for (int i=0;i<10;i++)
		{
			if (T[u].next[i])
			{
				if (u==root)
				{
					T[T[u].next[i]].fail=root;
				}
				else
				{
					v=T[u].fail;
					while (v)
					{
						if (T[v].next[i])
						{
							T[T[u].next[i]].fail=T[v].next[i];
							break;
						}
						v=T[v].fail;
					}
					if (!v)
						T[T[u].next[i]].fail=root;
				}
				Q.push(T[u].next[i]);
			}
		}
	}
}
int matchAndDp(char *N,bool flag)
{
	int len=strlen(N),v;
	f[0][tT][1]=1;
	for (int i=0;i<len;i++)
	{
		for (int j=1;j<=tT;j++)
		{
			if (T[j].flag)
				continue;
			for (int k=0;k<10;k++)
			{
				v=j;
				while (v!=root && T[v].next[k]==0)
					v=T[v].fail;
				v=T[v].next[k];
				if (v==0)
					v=root;
				if (T[v].flag)
					continue;
				if (k<N[i]-'0')
				{
					(f[i+1][v][0]+=(f[i][j][0]+f[i][j][1])%mod)%=mod;
				}else if (k==N[i]-'0')
				{
					(f[i+1][v][0]+=f[i][j][0])%=mod;
					(f[i+1][v][1]+=f[i][j][1])%=mod;
				}else if (k>N[i]-'0')
				{
					(f[i+1][v][0]+=f[i][j][0])%=mod;
				}
			}
		}
	}
	int ans=0;
	for (int i=1;i<tT;i++)
		if (T[i].flag==false)
			(ans+=((f[len][i][0]+f[len][i][1])%mod))%=mod;
	return ans;
}
int main()
{
	char NN[1205],buf[1505];
	int m;
	memset(T,0,sizeof(T));
	scanf("%s%d",NN,&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%s",buf);
		trieInsert(buf);
	}
	trieBuild();
	tT++;
	T[tT].next[0]=tT;
	T[tT].fail=root;
	for (int i=1;i<10;i++)
		T[tT].next[i]=T[root].next[i];
	int len=strlen(NN);
	int ans=0;
	(ans+=matchAndDp(NN,1))%=mod;
	printf("%d\n",ans);
	return 0;
}
//这段代码同提交上去的代码相比，删除了注释和用于调试的函数