题目大意：求a到b之间的数满足翻译成bcd码后没有禁止串的个数。
题目思路：ac自动机加按位dp，需要注意的是，一般在a的长度比b短时，我们会进行加零处理，这样由于0是不存在的，匹配的时候前导0也不能进行匹配，需要特殊判断一下。
[cpp] #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define inf 0x3f3f3f3f #define Max 110 #define mod 1000000009 int max(int a,int b) { return a>b a:b; } int min(int a,int b) { return a } int q[25*110]; int cnt; char mp[20][10]={"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001"}; int up[300],down[300]; int dp[220][2][2][22*110]; int lena,lenb; struct node { int cnt,fail; int next[2]; void init() { cnt=fail=0; memset(next,0,sizeof(next)); } }tri[25*110]; void insert(char *s) { int i,p,x; p=0; for(i=0;s[i];i++) { x=s[i]-'0'; if(!tri[p].next[x]) { tri[++cnt].init(); tri[p].next[x]=cnt; } p=tri[p].next[x]; } tri[p].cnt++; } void bfs() { int i,p,head,tail,suf; p=0; head=tail=0; for(i=0;i<2;i++) { if(tri[0].next[i]) { q[tail++]=tri[0].next[i]; tri[q[tail-1]].fail=0; } } while(head { p=q[head++],suf=tri[p].fail; tri[p].cnt+=tri[suf].cnt; for(i=0;i<2;i++) { if(tri[p].next[i]) { q[tail++]=tri[p].next[i]; tri[q[tail-1]].fail=tri[suf].next[i]; } else tri[p].next[i]=tri[suf].next[i]; } } } int dfs(int pos,int bg,int sl,int k) { if(pos==lenb) return 1; int ans=0,i,j,l,r,x,tmp; if(dp[pos][bg][sl][k]!=-1) return dp[pos][bg][sl][k]; ans=0; l=bg 0:down[pos]; r=sl 9:up[pos]; for(i=l;i<=r;i++) { tmp=k; if(pos>=lenb-lena||bg||i) { for(j=0;j<4;j++) { x=mp[i][j]-'0'; tmp=tri[tmp].next[x]; if(tri[tmp].cnt) break; } } if(tri[tmp].cnt) continue; ans=(ans+dfs(pos+1,bg|(i>down[pos]),sl|(i } dp[pos][bg][sl][k]=ans; return ans; } char str[100],a[300],b[300],c[300]; int main() { int i,t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(dp,-1,sizeof(dp)); cnt=0; tri[0].init(); while(n--) { scanf("%s",str); insert(str); } bfs(); scanf("%s%s",a,b); lena=strlen(a); lenb=strlen(b); if(lena { strcpy(c,a); for(i=0;i a[i]='0'; a[lenb-lena]=0; strcat(a,c); } for(i=0;i { down[i]=a[i]-'0'; up[i]=b[i]-'0'; } printf("%d\n",dfs(0,0,0,0)); } }