BZOJ3530/SDOI2014/数数

Posted on By 二价氢

#题目描述

#做法

AC自动机+DP

我们用表示当前是第位,在自动机的状态上,用串的前缀是否等于的前缀

假设,

最后答案就是

这里有一个问题,就是如果给定的字符串集合含有前导0,那么我们就会发现,本来表示不存在的0这里突然被占用,导致大量合法的“幸运数”被判为非法

我的做法是,建立一个超级起点,它的状态转移是像下面这个表这样的:

0 1 2 3 4 5 6 7 8 9 fail
SS S.1 S.2 S.3 S.4 S.5 S.6 S.7 S.8 S.9 S

注意加粗的部分,可以看出,这个超级起点除了对0的输入不一样之外,其余的全部一样,从而0就被困在里面,不会被计入答案,同时,如果想离开超级起点,就必须给予一个非零输入,进入别的点,这样就相当于删除了所有的前导0

完美解决问题

另外,这题的数据中,有8个点的S集合里的数是不带前导0的,由此我们可以看出出题人的良苦用心

#AC Code

#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;
}