[bzoj3530][Sdoi2014]数数_AC自动机

数数 bzoj-3530 Sdoi-2014

题目大意：给你一个整数集合，求所有不超过n的正整数，是的它的十进制表示下不能再一段等于集合中的任意数。

注释：$1\le n \le 1200$，$1\le |S|\le 100$，$1\le L\le 1500$，L是总长度之和。

想法：咳咳，显然，我们... ...什么都不想，看着能开下先把AC自动机扔出来

然后，其实数位dp就可以了

具体看代码

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#define mod 1000000007

using namespace std;

typedef long long ll;

struct tree

{

	int fail;

	int vis[11];

	int end;

}a[1600];

char s[1600],t[1250];

int n,m,cnt;

ll f[3][1250][1600],ans;

void build(char *s)

{

	int l=strlen(s);

	int now=0;

	for(int i=0;i<l;i++)

	{

		int x=s[i]-'0';

		if(!a[now].vis[x])

		{

			a[now].vis[x]=++cnt;

		}

		now=a[now].vis[x];

	}

	a[now].end|=1;

}

queue<int>q;

void getfail()

{

	while(!q.empty()) q.pop();

	for(int i=0;i<10;i++)

	{

		if(a[0].vis[i]!=0)

		{

			a[a[0].vis[i]].fail=0;

			q.push(a[0].vis[i]);

		}

	}

	while(!q.empty())

	{

		int now=q.front();q.pop();

		for(int i=0;i<10;i++)

		{

			if(!a[now].vis[i])

			{

				a[now].vis[i]=a[a[now].fail].vis[i];

			}

			else

			{

				a[a[now].vis[i]].fail=a[a[now].fail].vis[i];

				a[a[now].vis[i]].end|=a[a[a[now].fail].vis[i]].end;

				q.push(a[now].vis[i]);

			}

		}

	}

}

int main()

{

	scanf("%s",t+1);

	m=strlen(t+1);

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%s",s),build(s);

	getfail();

	for(int i=0;i<m;i++)

	{

		for(int j=0;j<=cnt;j++)

		{

			if(!j)

			{

				if(!i)

				{

					int x=t[i+1]-'0';

					for(int k=1;k<x;k++)

					{

						if(!a[a[j].vis[k]].end)

						{

							f[1][i+1][a[j].vis[k]]+=1;

							f[1][i+1][a[j].vis[k]]%=mod;

						}

					}

					if(!a[a[j].vis[x]].end)

					{

						f[0][i+1][a[j].vis[x]]+=1;

						f[0][i+1][a[j].vis[x]]%=mod;

					}

				}

				else

				{

					for(int k=1;k<=9;k++)

					{

						if(!a[a[j].vis[k]].end)

						{

							f[1][i+1][a[j].vis[k]]++;

							f[1][i+1][a[j].vis[k]]%=mod;

						}

					}

				}

			}

			if(f[0][i][j])

			{

				int x=t[i+1]-'0';

				for(int k=0;k<x;k++)

				{

					if(!a[a[j].vis[k]].end)

					{

						f[1][i+1][a[j].vis[k]]+=f[0][i][j];

						f[1][i+1][a[j].vis[k]]%=mod;

					}

				}

				if(!a[a[j].vis[x]].end)

				{

					f[0][i+1][a[j].vis[x]]+=f[0][i][j];

					f[0][i+1][a[j].vis[x]]%=mod;

				}

			}

			if(f[1][i][j])

			{

				for(int k=0;k<=9;k++)

				{

					if(!a[a[j].vis[k]].end)

					{

						f[1][i+1][a[j].vis[k]]+=f[1][i][j];

						f[1][i+1][a[j].vis[k]]%=mod;

					}

				}

			}

		}

	}

	for(int i=0;i<=cnt;i++)

	{

		ans+=f[0][m][i];

		ans%=mod;

		ans+=f[1][m][i];

		ans%=mod;

	}

	printf("%lld\n",ans);

	return 0;

}

小结：我们在处理字符串问题的时候脑子里先有几个数据结构在搞事情.. ...

巴特西

[bzoj3530][Sdoi2014]数数_AC自动机_数位dp

最新文章

热门文章