HDU4507(数位dp，模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<cstring>
#define ll long long
//#define mod 1000000007LL
using namespace std;
ll mod=1e9 + 7;
ll d[20],p[20];//这边用int会超 
struct node
{
	ll sqnum,cnt,num;
	node(){
		cnt=-1;num=sqnum=0;
	}
	node(ll a,ll b,ll c):cnt(a),num(b),sqnum(c){
	}
}dp[20][8][8];
node dfs(int l,int h,int s,bool lim)
{
	if(l==0) return (h!=0&&s!=0)? node(1,0,0):node(0,0,0);//注意，求得是和7无关的 
	if(!lim&&dp[l][h][s].cnt!=-1) return dp[l][h][s];//如果没有限制了并且dp[l][h][s]前面已经得出答案了，就直接返回 
	int k= lim? d[l]:9;//如果有限制，那就最多到d[l]，即后面的枚举要小于l位数 
	node tp,r=node(0,0,0);
	for(int i=0;i<=k;i++)
	{
		if(i==7) continue;
		tp=dfs(l-1,(h+i)%7,(s*10+i)%7,lim&&i==d[l]);//只有前面的数都恰好等于给定数的值，那么后面的数才是有限制的 
		r.cnt+=tp.cnt;//加上后面位中符合条件的数 
		r.cnt%=mod;
		r.num+=(tp.num+((p[l]*i)%mod)*tp.cnt%mod)%mod;//反正各种记录 
        r.num%=mod;
        r.sqnum+=(tp.sqnum+((2*p[l]*i)%mod)*tp.num)%mod;
        r.sqnum%=mod;
        r.sqnum+=((tp.cnt*p[l])%mod*p[l]%mod*i*i%mod);
        r.sqnum%=mod;
	}
	if(!lim)
	dp[l][h][s]=r;
	return r;
}
 
ll solve(ll a)
{
	int l=0;
	while(a)
	{
		d[++l]=a%10;
		a/=10;
	}
	node tp=dfs(l,0,0,true);
	return tp.sqnum;
}
int main()
{
	freopen("t.txt","r",stdin);
	ll T,a,b;
	scanf("%d",&T);
	p[1]=1;
    for(int i=2;i<=20;i++) p[i]=(p[i-1]*10)%mod;
    //printf("%lldn",mod); 
	while(T--)
	{
		scanf("%lld%lld",&a,&b);
		ll ans=solve(b)-solve(a-1);
		printf("%lldn",(ans%mod+mod)%mod);//可能两个相减为负数，所以要变成正的 
	}
	return 0;
}