题目链接：zoj3494
题解：把给的串建ac自动机，然后得到的bcd[i][j]，bcd[i][j]表示在AC自动机上的状态i,后面加入j会转移的状态，-1表示不能加
然后数位dp,dp[i][j]表示取到第i位状态为j后面的数字随便取的方案数，这里是记忆化。
#include<bits/stdc++.h> #include<set> #include<cstdio> #include<iomanip> #include<iostream> #include<string> #include<cstring> #include<algorithm> #define pb push_back #define mk make_pair #define ll long long #define fi first #define se second #define PI 3.14159265 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define eps 1e-7 #define pii pair<int,int> #define pll pair<ll,ll> typedef unsigned long long ull; const int mod=1000000009; const ll inf=0x3f3f3f3f3f3f3f; const int N=2e3+100; using namespace std; char s[300]; int n; struct ac_auto { int nxt[N][2],ed[N],fail[N],cn,rt; ac_auto(){} void init(){ memset(nxt,-1,sizeof(nxt)); memset(ed,0,sizeof(ed)); memset(fail,-1,sizeof(fail)); cn=0; rt=new_node(); } int new_node() { return cn++; } void insert(char *s) { int len=strlen(s); int p=rt; for(int i=0;i<len;i++) { int x=s[i]-'0'; if(nxt[p][x]==-1)nxt[p][x]=new_node(); p=nxt[p][x]; } ed[p]=1; } void build() { queue<int>q; fail[rt] = rt; for(int i = 0;i < 2;i++) if(nxt[rt][i] == -1) nxt[rt][i] = rt; else { fail[nxt[rt][i]] = rt; q.push(nxt[rt][i]); } while(!q.empty()) { int now = q.front(); q.pop(); if(ed[fail[now]])ed[now] = true; for(int i = 0;i < 2;i++) if(nxt[now][i] == -1) nxt[now][i] = nxt[fail[now]][i]; else { fail[nxt[now][i]] = nxt[fail[now]][i]; q.push(nxt[now][i]); } } } }ac; int bcd[N][10]; int judge(int x,int y) { if(ac.ed[x])return -1; for(int i=3;i>=0;i--) { if(ac.ed[ac.nxt[x][(y>>i)&1]])return -1; x=ac.nxt[x][(y>>i)&1]; } return x; } void slove() { for(int i=0;i<ac.cn;i++) { for(int j=0;j<10;j++) { bcd[i][j]=judge(i,j); } } } ll dp[210][N]; int bit[300]; ll dfs(int p,int s,int flag,int z)//p第几位，s当前的状态，flag是否已经有高位小于s,前面是否有非0值 { if(p==-1)return 1; if(!flag&&dp[p][s]!=-1)return dp[p][s]; ll ans=0; if(z) { ans+=dfs(p-1,s,0,1); ans%=mod; } else { if(bcd[s][0]!=-1)ans+=dfs(p-1,bcd[s][0],flag&&bit[p]==0,0); ans%=mod; } int lim=(flag?bit[p]:9); for(int i=1;i<=lim;i++) { if(bcd[s][i]!=-1)ans+=dfs(p-1,bcd[s][i],flag&&i==bit[p],0); ans%=mod; } if(!flag&&!z)dp[p][s]=ans; return ans; } ll get(char *s) { int len=strlen(s); for(int i=0;i<len;i++) { bit[i]=s[len-1-i]-'0'; } return dfs(len-1,0,1,1); } int main() { int T; scanf("%d",&T); while(T--) { memset(dp,-1,sizeof(dp)); ac.init(); scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%s",s); ac.insert(s); } ac.build(); slove(); scanf("%s",s); int len=strlen(s); for(int i=len-1;i>=0;i--) { if(s[i]>'0') { s[i]--;break; } else s[i]='9'; } ll ans=0; ans-=get(s); ans%=mod; scanf("%s",s); ans+=get(s); ans%=mod; if(ans<0)ans+=mod; printf("%lld ",ans); } return 0; } /* 1 2 1 2 1 2 1 1 1 2 1 2 */