吉哥系列故事——恨7不成妻

思路：

区间内找出不含7的个数以及区间这些数的和都是数位 $dp$ 的板子题，求区间内不含7的数的平方和需要推导公式。
数位 $dp$ 求 $len$ 位数的结果时，是将 $len-1$ 位数的结果相加得到的。
这不像我们平时写的那些数位题只求满足条件的数的个数，所以我们可以考虑设成结构体数组， $cnt$ 存符合条件的个数， $sum$ 存符合条件的数的和， $ssum$ 存符合条件的数的平方和。

$dp[len][p1][p2]$ ,表示满足条件的 $len$ 位数的结果。

最高位到第 $len$ 位的位数和 $\%7$ 的值为 $p1$ ，最高位到第 $len$ 位的数值和 $\%7$ 的值为 $p2$

设 $x=digit[len]*inf[len]$ ，作用相当于：123，第3位是1，那么 $x=digit[3]*inf[3]=100$

那么 $ans.cnt+=son.cnt$ ， $ans.sum+=x*son.cnt+son.sum$

$ans$ 是存某个 $len$ 位数结果的结构体（第 $len$ 位是 $digit[len]$ ）， $son$ 是存ans后面某个 $len-1$ 位结果的结构体。

$123^2=(100+23)^2=100^2+2*100*23+23^2$ ,于是可以求 $ans.ssum=(x+son)^2$
$len-1$ 位数符合条件的数的平方和已经存过了，即 $son.ssum，可得表达式$
$ans.ssum=(x+son)^2=x^2+2*x*son.sum+son.ssum$
需要注意的是， $son$ 是包含多个数的，包含 $son.sum$ 个符合条件的数。

$limit$ 表示当前位数的结果是否有范围限制。

$1e8$ 是 $19$ 位数

MyCode:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7,mod=1e9+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll inf[20];
inline void init() {
    inf[1]=1;
    for(int i=2; i<=19; ++i)
        inf[i]=inf[i-1]*10%mod;
}
struct node {
    ll cnt,sum,ssum;
    node() {
        cnt=-1;
        sum=ssum=0;
    }
} dp[23][10][10];
int digit[23];
node dfs(int len,int p1,int p2,int limit) {//1.当前是几位数 2.数位和%7的值 3.数值%7的值
    node ans,tmp;
    if(!len) {
        ans.cnt=(p1&&p2);
        return ans;
    }
    if(!limit&&dp[len][p1][p2].cnt!=-1) return dp[len][p1][p2];
    int endi=(limit?digit[len]:9);
    ans.cnt=0;
    for(ll i=0; i<=endi; ++i) {
        if(i==7) continue;
        tmp=dfs(len-1,(p1+i)%7,(p2*10+i)%7,limit&&i==endi);
        ll x=i*inf[len]%mod;//当前最高位的值
        ans.cnt=(ans.cnt+tmp.cnt)%mod;
        ans.sum=(ans.sum+x*tmp.cnt%mod+tmp.sum)%mod;
        ans.ssum=(ans.ssum+x*x%mod*tmp.cnt%mod+2*x*tmp.sum%mod+tmp.ssum)%mod;
    }
    if(!limit) dp[len][p1][p2]=ans;
    return ans;
}
ll solve(ll x) {
    int len=0;
    while(x) {
        digit[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,0,1).ssum;
}
int main() {
    int t=read();
    init();
    while(t--) {
        ll l=read(),r=read();
        printf("%lld\n",(solve(r)-solve(l-1)+mod)%mod);
    }
    return 0;
}