本文主要是介绍HYSBZ - 3530 数数 【DP+AC自动机】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点我传送到题目！！！
题意：
给定一个数n，和m个数字构成的字符串，求1-n范围内不包含m个字符串中任何一个的数的个数？n的长度不超过1200，m不超过500。
解题思路：
这题可以用ac自动机来求是否包含字串，dp[i][j]表示第i位在ac机中状态为j的答案数。某一状态是否为匹配状态可以在AC机建立fail路径时建立预处理出来。
解题代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
#include<queue>
#include<vector>
#include<list>
#include<bitset>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;
struct Trie
{int nex[1510][11],fail[1510],end[1510];bool val[1205];int root,L;int newnode(){for(int i = 0; i < 11; i++)nex[L][i] = -1;val[L]=0;end[L++] = 0;return L-1;}void init(){L = 0;root = newnode();}void insert(char buf[]){int len = strlen(buf);int now = root;for(int i = 0; i < len; i++){if(nex[now][buf[i]-'0'] == -1)nex[now][buf[i]-'0'] = newnode();now = nex[now][buf[i]-'0'];}end[now]++;}void build(){queue<int>Q;fail[root] = root;val[root]=0;for(int i = 0; i < 10; i++)if(nex[root][i] == -1)nex[root][i] = root;else{int to=nex[root][i];fail[to] = root;val[to]=end[to];Q.push(nex[root][i]);}while( !Q.empty() ){int now = Q.front();Q.pop();//val[now]=end[now]>0;for(int i = 0; i < 10; i++)if(nex[now][i] == -1)nex[now][i] = nex[fail[now]][i];else{int to=nex[now][i];val[to]=end[to]>0;fail[to]=nex[fail[now]][i];val[to]|=val[fail[to]];Q.push(nex[now][i]);}}}
};
char buf[1505];
Trie ac;
int m;
int len;
int dig[1205];
char str[1205];
ll dp[1205][1510];
ll dfs(int p,int pos,int is,int flag)
{if(p==-1) return 1;if(dp[p][pos]!=-1&&!is&&flag) return dp[p][pos];int up=is?str[len-p-1]-'0':9;ll ret=0;for(int i=0;i<=up;i++){int f=flag||i!=0;int to=f?ac.nex[pos][i]:pos;if(!ac.val[to]) ret+=dfs(p-1,to,is&&i==up,f),ret%=mod;}if(!is&&flag) dp[p][pos]=ret;return ret;
}
ll get()
{len=strlen(str);ll ret=0;ret=dfs(len-1,ac.root,1,0);return ret-1;
}
int main()
{while(gets(str)){memset(dp,-1,sizeof dp);ac.init();scanf("%d",&m);getchar();for(int i=1; i<=m; i++){gets(buf);ac.insert(buf);}ac.build();int ans=get();printf("%d\n",ans);}return 0;
}
这篇关于HYSBZ - 3530 数数 【DP+AC自动机】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
