题目描述
单身!
依然单身！
吉哥依然单身！
DS级码农吉哥依然单身！
所以，他生平最恨情人节，不管是214还是77，他都讨厌！
吉哥观察了214和77这两个数，发现：
2+1+4=7
7+7=7*2
77=7*11
最终，他发现原来这一切归根到底都是因为和(7)有关！所以，他现在甚至讨厌一切和7有关的数！
什么样的数和(7)有关呢？
如果一个整数符合下面(3)个条件之一，那么我们就说这个整数和(7)有关——
- 整数中某一位是(7)；
- 整数的每一位加起来的和是(7)的整数倍；
- 这个整数是(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
数位(dp)题。
以前，我们遇到的数位(dp)题，都是求区间满足条件的数的个数。
那区间平方和怎么维护呢？
其实，区间平方和也可以做差求解。
那么，(dp)的同时需要维护(3)个值，开个结构体存一下就行了。
让我们一位位的进行计算。
1.满足条件的数的个数。这个利用普通的数位(dp)去维护就行了。
2.满足条件的数的和。这个维护时，加上子状态的值，以及该状态的位数和子状态的个数。
(12=(1*10^{1}+2*10^{0}))
因为我们枚举当前的位置(x)上放了(i)，则i在原数中对应(i*10^{x})
(1)是你当前枚举的数字，(2*10^{0})是你子状态的答案，所以状态的转移也就出来了。
当前sum=子状态sum+当前位的数字(10^{当前位数})子状态个数。
3.满足条件的数的平方和。这个维护时，加上子状态的值，以及该状态的位数和子状态的个数。
(12^{2}=(1*10^{1}+2*10^{0})^{2})
(12^{2}=1^{2}*(10^{1})^{2}+(2*10^{0})^{2}+2*(2*10^{0})*(1*10^{1}))
让我们回顾一下平方和公式：
((a+b)^{2}=a^{2}+b^{2}+2*a*b)
(a)就是当前位(i*10^{当前位数}),(b)是子状态和。
状态的转移也就出来了。
当前平方和=子状态平方和+(2*i∗10^{当前位数}*子状态和)+((i∗10^{当前位数})^{2}*子状态个数)
注意，取模后记得负数要加上模数再取模。
代码如下
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int mod=1000000007;
int T,num[25];
long long a,b,pow[20]={0,1};
struct node {
long long cnt,sum,qsum;
} dp[25][15][15];
node dfs(int pos,int mod1,int mod2,int limit) {
if(pos==0)return <%mod1&&mod2,0,0%>;
if(!limit&&dp[pos][mod1][mod2].cnt!=-1)return dp[pos][mod1][mod2];
int up=limit?num[pos]:9;
node res=<%0,0,0%>;
for(int i=0; i<=up; i++) {
if(i==7)continue;
node temp=dfs(pos-1,(mod1+i)%7,(mod2*10+i)%7,limit&(i==up));
res.cnt=(res.cnt+temp.cnt)%mod;
res.sum=(res.sum+temp.sum)%mod;
res.sum=(res.sum+((i*pow[pos])%mod)*temp.cnt%mod)%mod;
res.qsum=(res.qsum+temp.qsum%mod)%mod;
res.qsum=(res.qsum+((2*pow[pos]*i)%mod*temp.sum%mod)%mod)%mod;
res.qsum=(res.qsum+((pow[pos]*pow[pos])%mod*temp.cnt%mod*(i*i)%mod)%mod);
}
if(!limit)dp[pos][mod1][mod2]=res;
return res;
}
long long solve(long long n) {
int len=0;
while(n)num[++len]=n%10,n/=10;
return dfs(len,0,0,1).qsum;
}
int main() {
scanf("%d",&T);
for(int i=2;i<20;i++)pow[i]=(pow[i-1]*10)%mod;
for(int i=0; i<=20; i++)
for(int j=0; j<=10; j++)
for(int k=0; k<=10; k++)dp[i][j][k]=<%-1,0,0%>;
while(T--) {
scanf("%lld%lld",&a,&b);
printf("%lld
",(((solve(b)-solve(a-1))%mod+mod)%mod));
}
}