Description:

求区间 $[L,R]$ 内满足不是 $7$ 的倍数，每一位都不是 $7$ ，且各位数字之和不是 $7$ 的倍数的数的个平方和

$1\le T\le 30$ $1\le L \le R \le 10^{18}$

Solution:

数位 $DP​$ ， $f[i][j][k]​$ 表示第 $i​$ 位，数字为 $j(\%7)​$ ，各位数字之和为 $k(\%7)​$ ，需要记录三个量：个数 $cnt​$ ，和 $sum​$ ，平方和 $qsum​$ 。

对于这一位，设当前枚举的数字是 $i$ ，则对答案的贡献是 $\begin{align}\sum_{num=0}^{10^{pos}-1}(i\times10^{pos}+num)^2(num合法)\end{align}$ 。

$qsum_{cur}=\begin{align}\sum_{num=0}^{10^{pos}-1}(i\times10^{pos}+num)^2(num合法) \end{align}$

​ $\begin{align}=\sum_{num=0}^{10^{pos}-1}((i\times10^{pos})^2+2\times i\times10^{pos}\times num+num^2)(num合法)\end{align}$

​ $\begin{align}=\sum_{num=0}^{10^{pos}-1}(i\times10^{pos})^2+\sum_{num=0}^{10^{pos}-1}2\times i \times 10^{pos}\times num+\sum_{num=0}^{10^{pos}-1}num^2(num合法)\end{align}$

​ $\begin{align}=\sum_{i=0}^9((i\times10^{pos})^2\times cnt+2\times i \times 10^{pos}\times sum+qsum)\end{align}$

$\begin{align}sum_{cur}=\sum_{num=0}^{10^{pos}-1}(i\times 10^{pos}+num)\end{align}(num合法)$

​ $\begin{align}=\sum_{i=0}^{9}{sum+i\times 10^{pos}\times cnt}\end{align}$

$\begin{align} cnt_{cur}=\sum_{i=0}^{9}cnt\end{align}$

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 1000000007 

int testcases;

typedef long long ll;

ll l,r;

int bit[20];

struct state

{

	ll cnt,sum,qsum;

	state(ll a = 0,ll b = 0,ll c = 0){cnt = a;sum = b;qsum = c;}

};

state f[20][7][7];

bool v[20][7][7];

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = (res * a) % MOD;

		b = b >> 1;

		a = (a * a) % MOD;

	}

	return res;

}

state dfs(int pos,int num,int sum,bool bord)

{

	if(pos == 0)

	{

		return (state){((num != 0 && sum != 0) ? 1 : 0),0,0};

	}

	if(!bord && v[pos][num][sum])return f[pos][num][sum];

	int limit = (bord ? bit[pos] : 9);

	state res,tmp;

	ll sqr;

	for(int i = 0;i <= limit;++i)

	{

		if(i == 7)continue;

		tmp = dfs(pos - 1,(num * 10 + i) % 7,(sum + i) % 7,(bord && (i == limit)));

		sqr = (i * power(10ll,pos - 1)) % MOD;

		

		res.cnt = (res.cnt + tmp.cnt) % MOD;

		

		res.sum = ((res.sum + tmp.sum) % MOD + (sqr * tmp.cnt) % MOD) % MOD;

		

		res.qsum = (res.qsum + (sqr * sqr % MOD) * tmp.cnt % MOD) % MOD;

		res.qsum = (res.qsum + (sqr * 2) % MOD * tmp.sum % MOD) % MOD;

		res.qsum = (res.qsum + tmp.qsum) % MOD;

	}

	if(!bord){v[pos][num][sum] = true;f[pos][num][sum] = res;}

	return res;

}

ll calc(ll t)

{

	int len = 0;

	memset(bit,0,sizeof(bit));

	while(t > 0)

	{

		bit[++len] = t % 10;

		t /= 10;

	}

	memset(f,0,sizeof(f));

	memset(v,false,sizeof(v));

	return dfs(len,0,0,true).qsum;

}

int main()

{

	scanf("%d",&testcases);

	for(int i = 1;i <= testcases;++i)

	{

		cin >> l >> r;

		cout << (calc(r) - calc(l - 1) + MOD) % MOD << endl;

	}

	return 0;

}