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

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

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;
}