【BZOJ3530】数数（AC自动机，动态规划）

题面

题解

很套路的\(AC\)自动机+\(DP\)

首先，如果长度小于\(N\)

就不存在任何限制

直接大力\(DP\)

然后强制限制不能走到带有标记的点上面

如果长度恰好为\(N\)的长度

那么，要考虑是否恰好卡在范围里面

于是\(DP\)状态多记一维

表示是否卡在范围里面

最后求一下和就行啦

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 2000

#define MOD 1000000007

struct Node

{

	int vis[10];

	int lt,fail;

}t[MAX];

int tot,m;

char N[MAX],ch[MAX];

int f[MAX][MAX][2],g[MAX][MAX];

void insert(char *s)

{

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

	int l=strlen(s+1),now=0;

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

	{

		if(!t[now].vis[s[i]-48])

			t[now].vis[s[i]-48]=++tot;

		now=t[now].vis[s[i]-48];

	}

	t[now].lt=1;

}

void GetFail()

{

	queue<int> Q;

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

		if(t[0].vis[i])Q.push(t[0].vis[i]);

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		t[u].lt|=t[t[u].fail].lt;

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

			if(t[u].vis[i])

				t[t[u].vis[i]].fail=t[t[u].fail].vis[i],Q.push(t[u].vis[i]);

			else t[u].vis[i]=t[t[u].fail].vis[i];

	}

}

int main()

{

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

	scanf("%d",&m);

	while(m--)insert(ch);

	GetFail();

	int l=strlen(N+1);

	long long ans=0;

	g[0][0]=1;

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

		for(int u=0;u<=tot;++u)

			if(!t[u].lt)

			{

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

					if(!t[t[u].vis[k]].lt)

					{

						if(!i&&!k)continue;

						(g[i+1][t[u].vis[k]]+=g[i][u])%=MOD;

					}

			}

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

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

			ans=(ans+g[i][j])%MOD;

	f[0][0][1]=1;

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

		for(int u=0;u<=tot;++u)

			if(!t[u].lt)

			{

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

					if(!t[t[u].vis[k]].lt)

					{

						if(!i&&!k)continue;

						(f[i+1][t[u].vis[k]][0]+=f[i][u][0])%=MOD;

						if(k<N[i+1]-48)(f[i+1][t[u].vis[k]][0]+=f[i][u][1])%=MOD;

						if(k==N[i+1]-48)(f[i+1][t[u].vis[k]][1]+=f[i][u][1])%=MOD;

					}

			}

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

		ans=(ans+f[l][i][0])%MOD,ans=(ans+f[l][i][1])%MOD;

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

	return 0;

}

巴特西

【BZOJ3530】数数（AC自动机，动态规划）

【BZOJ3530】数数（AC自动机，动态规划）

题面

题解

最新文章

热门文章