[AC自动机+数位dp] zoj 3494 BCD Code

题意：需要将十进制数转换成二进制的BCD码。例如127=0001 0010 0111。

然后给你N个病毒串，，问十进制A~B范围内，转换成BCD码不含有任何一个病毒串的数有多少个。

思路：将这自动机和数位dp结合起来真是很巧妙。

其实也不难想。对于数位dp来说，我每次放i到某一位上的时候，其实就是进行了相应的节点移动。

比如我要放一个1，其实就是从当前节点往后顺着走了0->0->0->1，如果中途有节点被标记了，那就说明不能放1了。

然后就是大数减法不要写错了，最后就是，这是个减法的取模，所以前面有可能出现负数要处理一下。

代码：

#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"queue"#include"algorithm"#include"iostream"#include"map"#include"string"#define mod 1000000009#define ll long longusing namespace std;struct trie{int mark,id;trie *next[3],*fail;trie(){memset(next,0,sizeof(next));fail=NULL;mark=0;}};trie *root,*node[2234];int triecont;ll dp[222][2234];int num[222];char fuck[][10]= {"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001"};void init(char *v){trie *p=root;for(int i=0; v[i]; i++){int tep=v[i]-'0';if(p->next[tep]==NULL){p->next[tep]=new trie();p->next[tep]->id=triecont;node[triecont++]=p->next[tep];}p=p->next[tep];}p->mark=1;}void getac(){queue<trie*>q;q.push(root);while(!q.empty()){trie *p=q.front();q.pop();for(int i=0; i<2; i++){if(p->next[i]==NULL){if(p==root) p->next[i]=root;else p->next[i]=p->fail->next[i];}else{if(p==root) p->next[i]->fail=root;else p->next[i]->fail=p->fail->next[i];q.push(p->next[i]);if(p!=root) p->next[i]->mark|=p->next[i]->fail->mark;}}}}int ok(int jd,int x){trie *p=node[jd];for(int i=0; i<4; i++){int tep=fuck[x][i]-'0';if(p->next[tep]->mark==1) return -1;p=p->next[tep];}return p->id;}ll dfs(int site,int jd,int zero,int f){if(site==0){if(zero==0) return (ok(jd,0)!=-1);return 1;}if(!f&&dp[site][jd]!=-1) return dp[site][jd];ll ans=0;int len=f?num[site]:9;for(int i=0; i<=len; i++){if(zero==0&&i==0) ans+=dfs(site-1,jd,0,f&&i==len);else{int tep=ok(jd,i);if(tep==-1) continue;ans+=dfs(site-1,tep,1,f&&i==len);if(ans>=mod) ans%=mod;}}if(!f) dp[site][jd]=ans;return ans;}ll solve(char *v,int ok){int len=strlen(v);for(int i=0; v[i]; i++) num[i+1]=v[len-1-i]-'0';int i=1;if(ok==1){if(len==1&&num[i]==0) return 0;if(num[i]!=0) num[i]–;else{while(num[i]==0){num[i]=9;i++;}num[i]–;}}return dfs(len,0,0,1);}int main(){int t;cin>>t;while(t–){triecont=0;root=new trie();node[triecont]=root;root->id=triecont++;memset(dp,-1,sizeof(dp));int n;scanf("%d",&n);while(n–){char x[234];scanf("%s",x);init(x);}getac();char x[222],y[222];scanf("%s%s",x,y);ll ans=solve(y,0)-solve(x,1);printf("%lld\n",(ans%mod+mod)%mod);}return 0;}

怕仍是不能。于是他们比任何人都看的清楚，又比任何人都看的不确切。