记录编号	259832	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]简单的数位DP	最终得分	100
用户昵称	Aglove	是否通过	通过
代码语言	C++	运行时间	0.024 s
提交时间	2016-05-11 18:03:51	内存使用	0.99 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
const int mod=1e9+7;
int T;
int Num[22],len=0;
LL L,R;
LL t[22];
struct num{
	LL s0,s1,s2;
	void clear(){s0=s1=s2=0;}
}f[22][21][4][2][8];

void check(LL n){
	memset(Num,0,sizeof(Num));len=0;
	if(!n){Num[++len]=0;return;}
	while(n)Num[++len]=n%10,n/=10;
}
num DFS(int pos,int sum_mod,int L,int odd_tot,int num_mod,int flag){
	if(!pos){
		num tmp;tmp.clear();
		if(sum_mod!=0&&odd_tot==1&&num_mod!=0)tmp.s0=1;
		else tmp.s0=0;
		return tmp;
	}
	if(!flag&&f[pos][sum_mod][L][odd_tot][num_mod].s0!=-1)return f[pos][sum_mod][L][odd_tot][num_mod];
	num tmp;tmp.clear();
	int u=flag?Num[pos]:9;
	for(LL i=0;i<=u;++i){
		if(i==7)continue;
		
		int cur=L;
		if(cur==3){
			if(i==4)continue;
			if(i==3)cur=2;
			else cur=0;
		}else if(cur==2){
			if(i==1)cur=3;
			else cur=0;
		}else if(cur==1){
			if(i==3)cur=2;
			else cur=0;
		}
		if(cur==0)if(i==1)cur=1;
		
		LL sum=1LL*i*t[pos]%mod;
		num now=DFS(pos-1,(sum_mod+i)%21LL,cur,odd_tot^(i&1),(num_mod+1LL*i*t[pos])%8LL,flag&&i==u);
		
		tmp.s0=tmp.s0+now.s0;if(tmp.s0>=mod)tmp.s0-=mod;
		
		tmp.s1=tmp.s1+now.s1;if(tmp.s1>=mod)tmp.s1-=mod;
		tmp.s1=tmp.s1+now.s0*sum%mod;if(tmp.s1>=mod)tmp.s1-=mod;
		
		tmp.s2=tmp.s2+now.s2;if(tmp.s2>=mod)tmp.s2-=mod;
		tmp.s2=tmp.s2+now.s1*sum%mod*2LL%mod;if(tmp.s2>=mod)tmp.s2-=mod;
		tmp.s2=tmp.s2+now.s0*sum%mod*sum%mod;if(tmp.s2>=mod)tmp.s2-=mod;
	}return flag?tmp:f[pos][sum_mod][L][odd_tot][num_mod]=tmp;
}

int main(){
	freopen("get_num.in","r",stdin);
	freopen("get_num.out","w",stdout);
	t[1]=1;
	for(int i=2;i<=20;++i)t[i]=t[i-1]*10;
	scanf("%d",&T);
	memset(f,-1,sizeof(f));
	while(T--){
		scanf("%lld%lld",&L,&R);
		check(R);num A=DFS(len,0,0,0,0,1);
		check(L-1);num B=DFS(len,0,0,0,0,1);
		printf("%lld\n",(A.s2-B.s2+mod)%mod);
	}return 0;
}