转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526
by---cxlove
题目:给出一些模式串,给出一个范围[A,B],求出区间内有多少个数,写成BCD之后,不包含模式串
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3494
经典的AC自动机+数位DP。
好题,将这二者结合在了一起。。。ORZ
容易弄混的是BCD是二进制,而且并非普通的二进制,而我们的数为10进制。
这里就有一个转换,bcd[i][j]表示状态i经过数字j达到的合法状态
另外数位DP也是很经典,感觉数位DP的dfs写法非常好,通用
不过这题注意一下前导0的问题
另外需要注意的是我们求数位DP的话,需要把左区间-1,这里需要高精度-1
#include<iostream> #include<cstdio> #include<map> #include<cstring> #include<cmath> #include<vector> #include<algorithm> #include<set> #include<string> #include<queue> #define inf 1<<30 #define M 60005 #define N 10005 #define maxn 300005 #define eps 1e-10 #define zero(a) fabs(a)<eps #define Min(a,b) ((a)<(b)?(a):(b)) #define Max(a,b) ((a)>(b)?(a):(b)) #define pb(a) push_back(a) #define mem(a,b) memset(a,b,sizeof(a)) #define LL long long #define lson step<<1 #define rson step<<1|1 #define MOD 1000000009 using namespace std; struct Trie { Trie *next[2]; Trie *fail; int isword,kind; }; Trie *que[M],s[M]; int idx; char str[25]; int bcd[2005][10]; //bcd[i][j]表示在结点i,经过一个数字j,到达的结点 LL dp[205][2005]; //dp[i][j]表示长度为i,位于结点j的个数 int bit[205],len,n; Trie *NewNode() { Trie *tmp=&s[idx]; mem(tmp->next,NULL); tmp->isword=0; tmp->fail=NULL; tmp->kind=idx++; return tmp; } void Insert(Trie *root,char *s,int len) { Trie *p=root; for(int i=0; i<len; i++) { if(p->next[s[i]-'0']==NULL) p->next[s[i]-'0']=NewNode(); p=p->next[s[i]-'0']; } p->isword=1; } void Bulid_fail(Trie *root) { int head=0,tail=0; que[tail++]=root; root->fail=NULL; while(head<tail) { Trie *tmp=que[head++]; for(int i=0; i<2; i++) { if(tmp->next[i]) { if(tmp==root) tmp->next[i]->fail=root; else { Trie *p=tmp->fail; while(p!=NULL) { if(p->next[i]) { tmp->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL) tmp->next[i]->fail=root; } if(tmp->next[i]->fail->isword) tmp->next[i]->isword=tmp->next[i]->fail->isword; que[tail++]=tmp->next[i]; } else if(tmp==root) tmp->next[i]=root; else tmp->next[i]=tmp->fail->next[i]; } } } //状态当前在状态pre,经过一个数字num之后到达哪个状态 //如果不合法,返回-1 int BCD(int pre,int num) { if(s[pre].isword) return -1; int cur=pre; for(int i=3;i>=0;i--) { int k=(num>>i)&1; if(s[cur].next[k]->isword) return -1; else cur=s[cur].next[k]->kind; } return cur; } void Get_next() { for(int i=0;i<idx;i++) { for(int j=0;j<10;j++) { bcd[i][j]=BCD(i,j); } } } //数位DP,长度为len,当前状态为pos,是否有限制,是否有前导0 LL dfs(int len,int pos,bool limit,bool zero) { if(len==0) return 1; if(!limit&&dp[len][pos]!=-1) return dp[len][pos]; LL ans=0; //如果之前全为0,但是由于0是不能计算的,所以当前不为最低位 if(len>1&&zero) { ans+=dfs(len-1,pos,limit&&bit[len]==0,true); if(ans>=MOD) ans-=MOD; } else { //判断转移是否合法 if(bcd[pos][0]!=-1) ans+=dfs(len-1,bcd[pos][0],limit&&bit[len]==0,false); if(ans>=MOD) ans-=MOD; } int up=limit?bit[len]:9; for(int i=1;i<=up;i++) { if(bcd[pos][i]!=-1) { ans+=dfs(len-1,bcd[pos][i],limit&&i==up,false); if(ans>=MOD) ans-=MOD; } } if(!limit&&!zero) dp[len][pos]=ans; return ans; } LL cal(char *s,int l) { mem(dp,-1); for(int i=1;i<=l;i++) bit[l-i+1]=s[i-1]-'0'; dfs(l,0,true,true); } char A[205],B[205]; //高精度-1,这样会遗留前导0,无所谓了。。。 void sub(char *s,int len) { for(int i=len-1;i>=0;i--) { if(s[i]=='0') s[i]='9'; else { s[i]--; break; } } } int main() { int t; scanf("%d",&t); while(t--) { idx=0; Trie *root=NewNode(); scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%s",str); Insert(root,str,strlen(str)); } Bulid_fail(root); Get_next(); scanf("%s",A); sub(A,strlen(A)); LL ans=-cal(A,strlen(A)); scanf("%s",B); ans+=cal(B,strlen(B)); printf("%lld\n",(ans%MOD+MOD)%MOD); } return 0; }