文件详细信息

下载本文件

本文件的大小为 2378 字节。

/*
## 题目大意

如果一个整数符合下面三个条件之一，那么我们就说这个整数和 $7$ 有关：

1. 整数中某一位是 $7$；
2. 整数的每一位加起来的和是 $7$ 的整数倍；
3. 这个整数是 $7$ 的整数倍。

每次吉哥想知道在一定区间 $[l,r]$ 内和 7 无关的数字的平方和。答案对 $10^9+7$ 取模。

保证测试数据组数 $T \le 50$，$1 \le l,r \le 10^18$。

## 做法 1：数位 DP

数位和以及模 $7$ 的余数都很好解决，这道题唯一特别的一点就是要求平方和。我们发现，只要维护个数，就能维护一次方和（支持同时加上某一数这个操作），就能维护二次方和。
*/
#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef long long ll;
const int P=1000000007;
int T,pw10_7[20],pw10_P[20];
ll l,r;
int digit[20],cnt;
struct Data{
	int cnt,sum,sum2;
}f[20][7][7];
Data operator+(const Data a,const Data b){
	return Data{(a.cnt+b.cnt)%P,(a.sum+b.sum)%P,(a.sum2+b.sum2)%P};
}
Data operator+(const Data a,const int x){
	return Data{a.cnt,int((a.sum+(ll)a.cnt*x)%P),int((a.sum2+2ll*a.sum*x+(ll)a.cnt*x%P*x)%P)};
}
bool operator!=(const Data a,const Data b){
	return a.cnt!=b.cnt||a.sum!=b.sum||a.sum2!=b.sum2;
}
Data dfs(int cur,int lim,int sum,int remainder){
	if(cur==-1)return remainder&&sum?Data{1,0,0}:Data{0,0,0};
	if(!lim&&f[cur][sum][remainder]!=Data{-1,-1,-1})return f[cur][sum][remainder];
	int d=lim?digit[cur]:9;
	Data ans={0,0,0};
	for(int i=0;i<=d;i++)
		if(i!=7)
			ans=ans+(dfs(cur-1,lim&&i==d,(sum+i)%7,(remainder+pw10_7[cur]*i)%7)+((ll)i*pw10_P[cur]%P));
	if(!lim)f[cur][sum][remainder]=ans;
	return ans;
}
int solve(ll x){
	cnt=0;
	while(x){
		digit[cnt++]=x%10;
		x/=10;
	}
	memset(f,-1,sizeof(f));
	Data ans=dfs(cnt-1,1,0,0);
	return ans.sum2;
}
int main(){
	pw10_7[0]=1;
	for(int i=1;i<20;i++)pw10_7[i]=pw10_7[i-1]*10%7;
	pw10_P[0]=1;
	for(int i=1;i<20;i++)pw10_P[i]=pw10_P[i-1]*10ll%P;
	read(T);
	while(T--){
		read(l),read(r);
		write((P+solve(r)-solve(l-1))%P),putchar('\n');
	}
	return 0;
}