BCD Code

题意：
数字都要转为码，题目会给出个长度不超过的限制串，然后给出，求区间内有多少个数的码不包括限制串（）。有组数据。

这题卡了我几天，我这是用自动机数位解的，这题对自动机数位的应用都不深，都是简单的应用，但自动机我之前没学明白（写了一些题还是没明白），花几天又学了一遍，对自动机的结构更清楚了，找出了紫书模板有的部分是多余的，给自己重学一遍时理解代码思路增加了一些困难，也发现当初对模板的注释有些地方含糊不清（自己都看不懂，当时写注释的时候就是在强行解释），所以对模板以及注释都做了修改。

debug那些憨憨事：
用按字节初始化时，我用了上次计算留下的变量，但我在用这个变量之前把它初始化了，于是整个数组并没有初始化；没有特判前导零，前导零也加进去跑了一下，答案直接小了好多；，在串上跑十进制数的时候，我写的是;

思路：
1.将所有限制串做成一个字典树
2.求出这个字典树对应的数组（就是数组），同时标记限制串的结尾，如果这个节点是某个限制串的结尾（即它的指针指向的节点是某个限制串的结尾，或者它就是某个限制串的结尾），那么标记这个节点不能取。如果这个节点之前有节点被标记了，这个节点也要被标记。操作如下：

val[v]|=val[f[v]]|val[u];

3.将每一个被标记点的数组赋值成（抹去这个节点），表示这个节点不能取，取了就会有限制串

if(val[ch[i][0]]) ch[i][0]=-1;
if(val[ch[i][1]]) ch[i][1]=-1;

4.前面得到的数组都是在串上跑出来的，而为了方便后面搜索答案，需要将再用进制跑一遍串上的数组，得到一个数组可以叫它转移矩阵
5.一个进制数对应的码有四位，也就是一个十进制数对应四个节点，可以通过位运算处理：

for(j=0; j<=9; ++j) {
    for(now=i,k=8; k&&now!=-1; k>>=1)
        now=ch[now][(j&k)!=0];//(j&k)!=0判断二进制位是0还是1
    num[i][j]=now;
}//i是上一个状态，j是十进制数

准备工作都做好了，下面开始数位
1.，表示当前节点状态为,当前是否是前缀零，还可以走步有多少个合法的数
2.都是大数，得字符串读入，所以最高位下标最小，不做处理直接搜索，不符合平时数位的习惯（得到的状态对搜索的数据有依赖），所以通过这样的处理使得搜索时可以从大到小，这样求完的结果后，得到的状态可以用于求
3.每次输入的限制串都是不同的，所以上次计算的得到的状态不能用于求下一次计算，所以每次都需要初始化状态数组（这里我是另开一个数组标记这个状态是不是本次计算得到的，牺牲空间换时间）
4.最后再单独在上跑一遍字典树，如果出现了限制串，那么直接输出答案，否则说明多减了，也是符合要求的

注意：
1.如果当前位是前导零，那么继续往后搜索时有的点取不了，得到的结果可能会比不含前导零的少，所以状态数组多开了一维判断当前是不是前导零。
2.是唯一的
3.按字节初始化
4.前导零特判，如果是前导零就跳过，不要走过去了，前导零会对结果造成影响。

Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2003,mod=1000000009;
int n,m,sz,cas,len;
int ch[maxn][2],f[maxn],last[maxn],num[maxn][10];
int dp[maxn][202][2],lazy[maxn][202][2];
bool val[maxn];
char s[233];
inline void insert() {
    int u=0;
    for(int i=0,c; s[i]; i++) {
        c=s[i]-'0';
        u=ch[u][c]?ch[u][c]:(ch[u][c]=++sz);
    }
    val[u]=true;
}
inline void build() {
    queue<int>q;
    for(int c=0,u; c<=1; c++) {
        u = ch[0][c];
        if(u)  {
            f[u]=0;
            last[u] = 0;
            q.push(u);
        }
    }
    int u,v,c;
    while(!q.empty()) {
        u=q.front();
        q.pop();
        for(c=0; c<=1; c++) {
            v=ch[u][c];
            if(!v) {
                ch[u][c]=ch[f[u]][c];
                continue;
            }
            q.push(v);
            f[v] = ch[f[u]][c];
            val[v]|=val[f[v]]|val[u];
        }
    }
    for(int i=0; i<=sz; ++i) {
        if(val[ch[i][0]]) ch[i][0]=-1;
        if(val[ch[i][1]]) ch[i][1]=-1;
    }
    for(int i=0,j,k,now; i<=sz; ++i) if(!val[i]) {
            for(j=0; j<=9; ++j) {
                for(now=i,k=8; k&&now!=-1; k>>=1)
                    now=ch[now][(j&k)!=0];
                num[i][j]=now;
            }
        }
}
int dfs(int pos,int step,bool zero,bool limit) {
    if(!step) return !zero;
    if(!limit&&lazy[pos][step][zero]==cas) return dp[pos][step][zero];
    int endi=(limit?(s[len-step+1]-'0'):9),ans=0;
    if(zero) ans=dfs(pos,step-1,zero,limit&&0==endi);
    else if(num[pos][0]!=-1) ans=dfs(num[pos][0],step-1,zero,limit&&0==endi);
    for(int i=1; i<=endi; ++i) if(num[pos][i]!=-1) {
        ans+=dfs(num[pos][i],step-1,zero&&i==0,limit&&i==endi);
        if(ans>mod) ans-=mod;
    }
    if(!limit) {
        dp[pos][step][zero]=ans;
        lazy[pos][step][zero]=cas;
    }
    return ans;
}
int main() {
    int ans,now;
    for(scanf("%d",&cas); cas; --cas) {
        scanf("%d",&n);
        memset(val,false,sz+1);
        memset(ch,0,(sz+1)<<3);
        sz=0;
        for(int i=0; i<n; ++i) {
            scanf("%s",s);
            insert();
        }
        build();
        scanf("%s",s+1);
        len=strlen(s+1);
        now=num[0][s[1]-'0'];
        for(int i=2; i<=len&&now!=-1; ++i) now=num[now][s[i]-'0'];
        ans=(now!=-1)-dfs(0,len,true,true);
        scanf("%s",s+1);
        len=strlen(s+1);
        ans+=dfs(0,len,true,true);
        if(ans<0) ans+=mod;
        printf("%d\n",ans);
    }
    return 0;
}