学步园

转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526      
by---cxlove

给出一个区间，问这个区间内有多少个数不包含数字0，而且至少出现了一次A或者B

http://acm.bupt.edu.cn/onlinejudge/newoj/showProblem/show_problem.php?problem_id=652 

由于模式串只有两个，A,B其实可以直接匹配搞定吧，虽然我不会

还是老实用AC+数位DP吧，昨天做了ZOJ的BCD CODE，打算趁热把这题做了，结果跪了好久，哭~~~

自己对于数位DP理解不够，还有记忆化搜索

感觉数位DP的细节不好处理，比如说前导0，上下界之类的，现在尤其感觉前导0的问题

由于这题不能出现0，所以还需要注意，但是高位可以为0，也就是可以有前导0？？？

一直纠结于记忆化的问题，结果还是得用4维，dp[i][j][k][l]表示长度为i，当前在自动机的j结点，k表示是否高位全为0，l表示是否出现了指定串

#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[10];
    Trie *fail;
    int isword,kind;
};
Trie *que[M],s[M];
int idx;
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<10; 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];
        }
    }
}
char str[100];
LL L,R;
LL dp[20][55][2][2];
int bit[25],length,n;
LL dfs(int len,int pos,int flag,int zero,bool limit)
{
    if(len<=0) return flag==1;
    if(!limit&&flag&&dp[len][pos][zero][1]!=-1) return dp[len][pos][zero][1];
    if(!limit&&!flag&&dp[len][pos][zero][0]!=-1) return dp[len][pos][zero][0];
    LL ans=0;
    int up=limit?bit[len]:9;
    if(zero&&len>1) ans+=dfs(len-1,0,0,1,0==up);
    for(int i=1;i<=up;i++)
    {
        ans+=dfs(len-1,s[pos].next[i]->kind,flag||(s[pos].next[i]->isword),0,limit&&(i==up));
    }
    if(!limit)
    {
        dp[len][pos][zero][flag]=ans;
    }
    return ans;
}
LL slove(LL num)
{
    length=0;
    while(num)
    {
        bit[++length]=num%10;
        num/=10;
    }
    mem(dp,-1);
    return dfs(length,0,0,1,true);
}
int main()
{
    int t;
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        idx=0;Trie *root=NewNode();
        scanf("%lld%lld",&L,&R);
        scanf("%s",str);
        Insert(root,str,strlen(str));
        scanf("%s",str);
        Insert(root,str,strlen(str));
        Bulid_fail(root);
        printf("%lld\n",slove(R)-slove(L-1));
    }
    return 0;
}