本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15793528.html

题目链接

题目

单身！
依然单身！
吉哥依然单身！
DS 级码农吉哥依然单身！
所以，他平生最恨情人节，不管是 214214 还是 7777，他都讨厌！
吉哥观察了 214214 和 7777 这两个数，发现：
2+1+4=72+1+4=7
7+7=7×27+7=7×2
77=7×1177=7 × 11
最终，他发现原来这一切归根到底都是因为和 7777 有关！所以，他现在甚至讨厌一切和 77 有关的数！
什么样的数和 77 有关呢？如果一个整数符合下面三个条件之一，那么我们就说这个整数和 77 有关：
整数中某一位是 77；
整数的每一位加起来的和是 77 的整数倍；
这个整数是 77 的整数倍。
现在问题来了：吉哥想知道在一定区间内和 77 无关的数字的平方和。

思路

抛开平方和来说，这就是一道普通的数位dp。

但这题有平方和啊！

首先，假设当前这个数为 ab‾\overline{ab}，aa 为我们数位dp枚举的首位，bb 为后面的数，假设有 kk 位，然后让我们求在 aa 确定的情况下，所有 bb 的可能值下 ab‾\overline{ab} 的平方和，记为 Sab‾S_{\overline{ab}}

我们先用数位dp求一个 FbF_b，表示 bb 的方案数，于是上面的问题可以转化为：

Sab‾=∑Fb(ab‾)2\Large S_{\overline{ab}}=\sum^{F_b}(\overline{ab})^2

然后可以愉快地开始化简。

首先先把 ab‾\overline{ab} 变成一个数学式子：

Sab‾=∑Fb(a×10k+b)2\Large S_{\overline{ab}}=\sum^{F_b}(a\times 10^k+b)^2

后面有平方和公式拆开：

Sab‾=∑Fb(a2×102×k+2×a×10k×b+b2)\Large S_{\overline{ab}}=\sum^{F_b}(a^2\times 10^{2\times k}+2\times a\times 10^k\times b+b^2)

把 ∑Fb\sum^{F_b} 套进去：

Sab‾=Fb×a2×102×k+2×a×10k×∑Fbb+∑Fbb2\Large S_{\overline{ab}}=F_b\times a^2\times 10^{2\times k}+2\times a\times 10^k\times \sum^{F_b}b+\sum^{F_b}b^2

弄好看点：

Sab‾=Fba2102k+2×10ka∑Fbb+∑Fbb2\Large S_{\overline{ab}}=F_ba^210^{2k}+2\times10^ka\sum^{F_b}b+\sum^{F_b}b^2

显然 ∑Fbb2=Sb\sum^{F_b}b^2=S_b，因为这就是 SS 的定义：

Sab‾=Fba2102k+2×10ka∑Fbb+Sb\Large S_{\overline{ab}}=F_ba^210^{2k}+2\times10^ka\sum^{F_b}b+S_b

这个式子一看，还有 ∑Fbb\sum^{F_b}b 未知，怎么办？那我们就设 Tb=∑FbbT_b=\sum^{F_b}b。

于是式子就变成了这样：

Sab‾=Fba2102k+2×10kaTb+Sb\Large S_{\overline{ab}}=F_ba^210^{2k}+2\times10^kaT_b+S_b

然后我们来推一推 Tab‾T_{\overline{ab}} 吧。

Tab‾=∑Fbab‾\Large T_{\overline{ab}}=\sum^{F_b}\overline{ab}

拆一下 ab‾\overline{ab}：

Tab‾=∑Fb(a×10k+b)\Large T_{\overline{ab}}=\sum^{F_b}(a\times 10^k+b)

把 ∑Fb\sum^{F_b} 乘进去：

Tab‾=Fba10k+∑Fbb\Large T_{\overline{ab}}=F_ba10^k+\sum^{F_b}b

然后我们发现，∑Fbb\sum^{F_b}b 不就是 TbT_b 吗？然后套进去：

Tab‾=Fba10k+Tb\Large T_{\overline{ab}}=F_ba10^k+T_b

然后这道题就做成来了。

总结

这道题真得是一道不错的题。

很好的数位dp+推式子。

这道题推式子的过程有点烦，但我也明白，做数位dp的过程本质上就是个递归，每一步考虑一下自己本身，答案就是对的。

Code

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
68
// Problem: 1586：【 例 2】数字游戏
// Contest: SSOIER
// URL: http://ybt.ssoier.cn:8088/problem_show.php?pid=1586
// Memory Limit: 524 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
#define mo 1000000007
//#define N
int n, m, i, j, k; 
int x, y, a[30], ten[10010]; 
int f[30][10][10][2]; 
int s[30][10][10][2]; 
int t[30][10][10][2]; 

int dfs(int n, int sum, int x, int p)
{
	if(n==0) return f[n][sum][x][p]=((sum%7>0 && x%7>0) ? 1 : 0); 
	int i, k=0, F, S, T; 
	if(f[n][sum][x][p]!=-1) return f[n][sum][x][p]; 
	for(i=0; i<=9; ++i)
	{
		if(!p && i>a[n]) break; 
		if(i==7) continue; 
		k+=dfs(n-1, (sum+i)%7, (x*10+i)%7, p|(i<a[n])); k%=mo;  
		F=f[n-1][(sum+i)%7][(x*10+i)%7][p|(i<a[n])]; 
		S=s[n-1][(sum+i)%7][(x*10+i)%7][p|(i<a[n])]; 
		T=t[n-1][(sum+i)%7][(x*10+i)%7][p|(i<a[n])]; 
		t[n][sum][x][p]+=(ten[n-1]*i%mo*F%mo+T)%mo; 
		// printf("t[%lld][%lld][%lld][%lld]+=ten[%lld]*%lld*%lld+%lld\n", n, sum, x, p, n-1, i, F, T); 
		s[n][sum][x][p]+=(ten[n-1]*ten[n-1]%mo*i%mo*i%mo*F%mo+ten[n-1]*i%mo*T%mo*2%mo+S)%mo; 
		// printf("%lld %lld %lld %lld\n", n, S, T, s[n][sum][x][p]); 
		t[n][sum][x][p]%=mo; s[n][sum][x][p]%=mo; 
	}
	return f[n][sum][x][p]=k; 
}

int calc(int x)
{
	n=0; 
	memset(f, -1, sizeof(f)); 
	memset(s, 0, sizeof(s)); 
	memset(t, 0, sizeof(t)); 
	while(x) a[++n]=x%10, x/=10; 
	dfs(n, 0, 0, 0); 
	// printf("> %lld\n", s[n][0][0][0]); 
	return s[n][0][0][0]; 
}

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
	for(i=ten[0]=1; i<=10000; ++i) ten[i]=ten[i-1]*10%mo; 
	m=read(); 
	while(m--) x=read(), y=read(), printf("%lld\n", ((calc(y)-calc(x-1))%mo+mo)%mo); 
	return 0; 
}