hdu 4507 吉哥系列故事—

hdu 4507 吉哥系列故事——恨7不成妻

　　第一道数位dp的题目，没什么头绪，递归的算法参考了cxlove大神的写法，链接：http://blog.csdn.net/ACM_cxlove?viewmode=contents

　　不得不说数位dp是个神奇的算法，这个学会以后多校的很多题目应该就可以做了吧，记得有好多类似的题目><

　　思路：从最高位开始，每次多放一位，假设求12345，如果现在放了2位12***，那么剩下的可以分为2类，120**，121**，122**是没有限制的，后面的两个**可以取00~99，直接用长度为2的模板结果就可以了，这个是用记忆化搜索实现的，而123**则要限制下一位的数字，要继续到下一位再分类，所以如果不用递归的方法来做代码应该会很长。具体的做法如下：

HDU 4507

#include<stdio.h>
#include<string.h>
#define MOD 1000000007
int va[26];
long long Numcnt[20][7][7][2],Numsum[20][7][7][2],Numsum2[20][7][7][2];
long long numcnt,numsum,numsum2;//数字个数，数字和，数字平方和
long long Inv6,fa[20];

long long dfs(int pos,int x,int y,int z,int flag)//当前位，和除7的余数，数除7的余数，是否含有7
{
    if(!flag&&Numsum2[pos][x][y][z]!=-1)
    {
        numcnt=Numcnt[pos][x][y][z];
        numsum=Numsum[pos][x][y][z];
        return Numsum2[pos][x][y][z];
    }
    if(pos==0)    //所有位都放好了
    {
        if(!z&&x&&y)//如果前面没有7并且最后余数都不是0
            Numcnt[pos][x][y][z]=0;
        else
            Numcnt[pos][x][y][z]=1;
        Numsum[pos][x][y][z]=Numsum2[pos][x][y][z]=0;
        numcnt=Numcnt[pos][x][y][z];
        numsum=Numsum[pos][x][y][z];
        return Numsum2[pos][x][y][z];
    }
    int max=9;
    if(flag) max=va[pos];
    long long numcntnow=0,numsumnow=0,numsum2now=0;//当前位的对应个数
    for(int i=0;i<=max;i++)
    {
        int tx=(x+i)%7,ty=(y*10+i)%7,tz=((i==7)||z);
        numsum2=dfs(pos-1,tx,ty,tz,flag&&(i==max));
        long long temp=(i*fa[pos-1])%MOD;
        numcntnow=(numcntnow+numcnt)%MOD;
        numsumnow=((numsumnow+numsum)%MOD+(numcnt*temp)%MOD)%MOD;
        numsum2now=((numsum2now+numsum2)%MOD+(2*temp*numsum)%MOD+(((temp*temp)%MOD)*numcnt)%MOD)%MOD;
    }
    if(!flag)
    {
        Numcnt[pos][x][y][z]=numcntnow;
        Numsum[pos][x][y][z]=numsumnow;
        Numsum2[pos][x][y][z]=numsum2now;
    }
    numcnt=numcntnow;
    numsum=numsumnow;
    return numsum2now;
}

long long sum(long long n)
{
    long long x=(n%MOD*((n+1)%MOD))%MOD;
    x=x*((2*n+1)%MOD)%MOD;
    return x*Inv6%MOD;
}

long long cal(long long n)
{
    int lenth=1;
    while(n)
    {
        va[lenth++]=n%10;
        n/=10;
    }
    return dfs(lenth-1,0,0,0,1);
}

int main()
{
    int T;
    long long st,end;
    Inv6=166666668;
    fa[0]=1;
    for(int i=1;i<=19;i++)
    {
        fa[i]=(fa[i-1]*10)%MOD;
    }
    memset(Numsum2,-1,sizeof(Numsum2));
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d",&st,&end);
        long long ans=(sum(end)-sum(st-1))%MOD;
        ans=((ans-cal(end))%MOD+cal(st-1))%MOD;
        ans=(ans+MOD)%MOD;
        printf("%I64d\n",ans);
    }
    return 0;
}