题目：
单身!
依然单身！
吉哥依然单身！
DS级码农吉哥依然单身！
所以，他生平最恨情人节，不管是214还是77，他都讨厌！
吉哥观察了214和77这两个数，发现：
2+1+4=7
7+7=7*2
77=7*11
最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！
什么样的数和7有关呢？
如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——
1、整数中某一位是7；
2、整数的每一位加起来的和是7的整数倍；
3、这个整数是7的整数倍；
现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。
依然单身！
吉哥依然单身！
DS级码农吉哥依然单身！
所以，他生平最恨情人节，不管是214还是77，他都讨厌！
吉哥观察了214和77这两个数，发现：
2+1+4=7
7+7=7*2
77=7*11
最终，他发现原来这一切归根到底都是因为和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
题解：
1、不能出现7的话可以dfs遇到7就continue掉
2、每一位加起来不能是7的倍数，那么我们可以dfs过程中用一个参数来记录它的取余结果
又因为(a+b)%mod=(a%mod+b%mod)%mod,所以我们可以是缩减dp数组的大小
可能有人会有疑问，数位上各位相加最大才9*18.也就开大一点dp数组而已
但是要注意取余mod之后不仅仅缩减了dp数组的大小，还缩短了时间，因为这是在记忆化，范围越小越能大幅度优化时间复杂度
3、这个数也不能是7的倍数，那么就可以用秦九韶取余来优化
4、最难的就是我们最后求的结果是每一个数的平方和，大家都看到了数据范围是10^18(我记得有一种方法叫快速相乘，类似于快速幂，这里没有试这一种方法)
在网上找了一篇博客：http://www.freesion.com/article/9575132166/
代码：
1 #include<stdio.h>
2 #include<string.h>
3 #include<algorithm>
4 #include<iostream>
5 using namespace std;
6 const int maxn=105;
7 const int mod = 1e9+7;
8 typedef long long ll;
9 struct DP
10 {
11 ll cnt, sum, sqsum;
12 DP () {}
13 DP (ll cnt, ll sum, ll sqsum): cnt(cnt), sum(sum), sqsum(sqsum) {}
14 }dp[20][10][10];
15 //dp[x][y][z]表示在数字的第x位上，且各位数字之和取余7得结果(不取余直接存的话会内存超限)为y，目前这个数取余7结果
16 //(什么叫目前这个数，就是你第一位枚举的是1第二位枚举的是2，那么就是12)
17 //然后题目要求我们最后求的结果是“所有可行数的平方和取余于mod”，这个时候肯定不能直接平方
18 //由(a+b)^2=a^2+b^2+2ab,那么一个二位数(xy)=x*10+y;(xy)^2=(x*10+y)^2
19 //那么一个多位数也可以通过递归方式来求他的平方
20 //参考链接：http://www.freesion.com/article/9575132166/
21 ll tend[20];
22 ll v[maxn];
23 DP dfs(ll pos, ll mod1, ll mod2, bool limit)
24 {
25 if (pos == -1) return DP(mod1!=0 && mod2!=0, 0, 0);
26 if (!limit && dp[pos][mod1][mod2].cnt != -1) return dp[pos][mod1][mod2];
27
28 ll up=limit?v[pos]:9;
29 DP ans=DP(0,0,0);
30 for(ll i=0;i<=up;++i)
31 {
32 if(i==7) continue;
33 DP t = dfs(pos-1, (mod1+i)%7, (mod2*10+i)%7, limit&&(i==up));
34 ans.cnt += t.cnt;
35 ans.cnt %= mod;
36
37 ans.sum += t.sum + t.cnt*i%mod*tend[pos]%mod;
38 ans.sum %= mod;
39
40 ans.sqsum += t.cnt*i*i%mod*tend[pos]%mod*tend[pos]%mod;
41 ans.sqsum += t.sqsum + 2*i*tend[pos]%mod*t.sum%mod;
42 ans.sqsum %= mod;
43 }
44 if (!limit) dp[pos][mod1][mod2] = ans;
45 return ans;
46 }
47 ll solve(ll ans)
48 {
49 ll pos=0;
50 while(ans)
51 {
52 v[pos++]=ans%10;
53 ans/=10;
54 }
55 return dfs(pos-1,0,0,true).sqsum;
56 }
57 int main()
58 {
59 ll t,l,r;
60 tend[0]=1;
61 for (ll i = 1; i < 20; i++)
62 tend[i] = (tend[i-1]*10)%mod;
63 scanf("%I64d",&t);
64 memset(dp,-1,sizeof(dp));
65 while(t--)
66 {
67
68 scanf("%I64d%I64d",&l,&r);
69 printf("%I64d\n",(solve(r)-solve(l-1)+mod)%mod);
70 }
71 return 0;
72 }