首页 > 代码库 > ZOJ 3494 (AC自动机+高精度数位DP)
ZOJ 3494 (AC自动机+高精度数位DP)
题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3494
题目大意：给定一些被禁止的BCD码。问指定范围内不含有任何这些禁止的BCD码的数的个数。
解题思路：
AC自动机部分：
首先insert这些被禁止的BCD码。
然后打一下自动机前后状态的转移的表，用BCD[i][j]表示自动机状态i时，下一个数字是j的自动机的下一个状态。
一开始我考虑最先dfs的位在自动机的位置，后来发现SB了。AC自动机有一个root状态，也就是自动机位置为0的状态，使用这个0就行了。
即f函数中dfs(len,0,true,true)，每次由root状态出发，无须再考虑其它的。
数位DP部分：
本题的范围是高精度范围，所以需要特有的高精度写法。
麻烦的在于f(l-1)，要为高精度手艹一个-1，有种偷懒的写法，不过会导致出现前导0。
所以在传统的dfs中需要增加一个前导0的判断。
方法是：追加一个bool z，
在原有的0~9基础上，单独考虑0，
if(z) 则单独dfs前导0
否则dfs正常的0，1~9照常dfs。当然还需要判断当前状态s的下一个状态BCD[s][i]是否符合要求。
然后最后就是注意一下负数mod。
#include "cstdio"#include "cstring"#include "queue"#include "iostream"using namespace std;#define maxp 25*105#define mod 1000000009struct Trie{ Trie *next[2],*fail; int cnt;}pool[maxp],*root,*sz;int BCD[maxp][10],digit[205],ccnt;long long dp[205][maxp];Trie *newnode(){ Trie *ret=sz++; memset(ret->next,0,sizeof(ret->next)); ret->fail=0; ret->cnt=0; return ret;}void init(){ sz=pool; root=newnode();}void Insert(string str){ Trie *pos=root; for(int i=0;i<str.size();i++) { int c=str[i]-‘0‘; if(!pos->next[c]) pos->next[c]=newnode(); pos=pos->next[c]; } pos->cnt++;}void getfail(){ queue<Trie *> Q; for(int c=0;c<2;c++) { if(root->next[c]) { root->next[c]->fail=root; Q.push(root->next[c]); } else root->next[c]=root; } while(!Q.empty()) { Trie *x=Q.front();Q.pop(); for(int c=0;c<2;c++) { if(x->next[c]) { x->next[c]->fail=x->fail->next[c]; x->next[c]->cnt+=x->fail->next[c]->cnt; Q.push(x->next[c]); } else x->next[c]=x->fail->next[c]; } }}int judge(int status,int num){ Trie *pos=pool+status; if(pos->cnt) return -1; for(int i=3;i>=0;i--) { if(pos->next[(num>>i)&1]->cnt) return -1; else pos=pos->next[(num>>i)&1]; } return pos-pool;}void getbcd(){ for(int i=0;i<ccnt;i++) for(int j=0;j<10;j++) BCD[i][j]=judge(i,j);}int dfs(int len,int s,bool fp,bool z){ if(!len) return 1; if(!fp&&dp[len][s]!=-1) return dp[len][s]; long long ret=0; int fpmax=fp?digit[len]:9; if(z) { ret+=dfs(len-1,s,fp&&digit[len]==0,true); ret%=mod; } else { if(BCD[s][0]!=-1) ret+=dfs(len-1,BCD[s][0],fp&&digit[len]==0,false); ret%=mod; } for(int i=1;i<=fpmax;i++) { if(BCD[s][i]!=-1) ret+=dfs(len-1,BCD[s][i],fp&&i==fpmax,false); ret%=mod; } if(!fp&&!z) dp[len][s]=ret; return ret;}int f(string str){ int len=0; for(int i=str.size()-1;i>=0;i--) digit[++len]=str[i]-‘0‘; return dfs(len,0,true,true);}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); int T,n; string tt; cin>>T; while(T--) { init(); memset(dp,-1,sizeof(dp)); cin>>n; for(int i=1;i<=n;i++) { cin>>tt; Insert(tt); } getfail(); ccnt=sz-pool; getbcd(); cin>>tt; for(int i=tt.size()-1;i>=0;i--) { if(tt[i]>‘0‘) {tt[i]--;break;} else {tt[i]=‘9‘;} } long long ans=0; ans-=f(tt); ans%=mod; cin>>tt; ans+=f(tt); ans=(ans%mod+mod)%mod; printf("%lld\n",ans); }}
| 2842327 | neopenx | ZOJ 3494 | Accepted | 4656 KB | 210 ms | C++ (g++ 4.4.5) | 2976 B | 2014-10-13 17:06:35 |
ZOJ 3494 (AC自动机+高精度数位DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。