吉哥系列故事——恨7不成妻 数位dp

单身!
　　依然单身！
　　吉哥依然单身！
　　DS级码农吉哥依然单身！
　　所以，他生平最恨情人节，不管是214还是77，他都讨厌！
　　
　　吉哥观察了214和77这两个数，发现：
　　2+1+4=7
　　7+7=72
　　77=711
　　最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！

什么样的数和7有关呢？

如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——
　　1、整数中某一位是7；
　　2、整数的每一位加起来的和是7的整数倍；
　　3、这个整数是7的整数倍；

现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。
Input
输入数据的第一行是case数T(1 <= T <= 50)，然后接下来的T行表示T个case;每个case在一行内包含两个正整数L, R(1 <= L <= R <= 10^18)。
Output
请计算[L,R]中和7无关的数字的平方和，并将结果对10^9 + 7 求模后输出。
Sample Input
3
1 9
10 11
17 17
Sample Output
236
221
0
思路：对于一个数可以从中间断开写成aa+bb+2ab的格式，开三个数组，一个记接下来的个数，一个记接下来的平方和，一个记接下来的和，顺着推回去就行了

#include<stdio.h>
#include<cstring>
const int mod=1e9+7;
typedef long long ll;
long long dp[20][10][10],dp1[20][10][10],dp2[20][10][10];
int a[20];
ll p[20];
ll dfs(int pos,int fjia,int fhong,bool limit,ll &ss,ll &dd,ll &cc){
   
	if(pos==-1){
   
		dd=0; ss=0;
		if(fjia!=0&&fhong!=0)	cc=1;
		else cc=0;
		return dd;
	}
	if(!limit&&dp2[pos][fjia][fhong]!=-1){
   
		ss=dp1[pos][fjia][fhong];
		dd=dp2[pos][fjia][fhong];
		cc=dp[pos][fjia][fhong];
		return dp2[pos][fjia][fhong];
	}
	int up=limit?a[pos]:9;
	ss=0,dd=0,cc=0;
	ll s,d,c;
	for(int i=0;i<=up;i++){
   
		if(i==7)	continue;
		dfs(pos-1,(fjia+i)%7,(fhong*10+i)%7,limit&&up==i,s,d,c);
		ll k=i*p[pos]%mod;
		cc=(cc+c)%mod;
		ss=(((c*k%mod)+s)%mod+ss)%mod;
        dd=((c*k%mod*k%mod)%mod+d%mod+2*k*s%mod+dd%mod)%mod;
	}
	if(!limit){
   
        dp1[pos][fjia][fhong]=ss;
        dp[pos][fjia][fhong]=cc;
        dp2[pos][fjia][fhong]=dd;
    }
    return dd;
}
ll solve(ll x){
   
	int pos=0;
	while(x){
   
		a[pos++]=x%10;
		x/=10;	
	}
	ll s,d,c;
	return dfs(pos-1,0,0,true,s,d,c);
}
int main(){
   
	int t;
	memset(dp2,-1,sizeof(dp2));
	scanf("%d",&t);
	p[0]=1;
    for(int i=1;i<20;i++)
        p[i]=p[i-1]*10%mod;
	while(t--){
   
		ll x,y;
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",((solve(y)-solve(x-1))%mod+mod)%mod);
	}
	return 0;
}