题面简述

题目链接

如果一个整数符合下面\(3\)个条件之一，那么我们就说这个整数和7有关——
　　1、整数中某一位是\(7\)；
　　2、整数的每一位加起来的和是\(7\)的整数倍；
　　3、这个整数是\(7\)的整数倍；

现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。

\(l,r\leq 10^{18}\)

具体请见题目

题解

典型的数位dp题目。

考虑\(f[p,s,v]\)表示数位\(p\)，各位和对\(7\)取模是\(s\)，数对\(7\)取模是\(v\)的方案数。

那么在搜索的过程中只要避开\(7\)的分支，并在搜到叶节点的时候判断是否满足条件\(2,3\)即可。

如果是和显然很好求。平方和需要用到额外的东西。

完全平方公式。

大概是初二的时候教了这东西吧。完全没想到它。\((a+b)^2=a^2+b^2+2ab\)

那么利用这个公式。我们就可以在中途维护这个平方和了。

对\(f\)数组维护三个量：\(cnt\)表示合法的数的个数，\(sum\)表示合法的数的和，\(sumq\)表示合法的数的平方和。

那么在回溯过程中对\(cnt\)和\(sum\)累加，对\(sumq\)利用完全平方公式处理即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;

ll num[23], cnt, po[23];
ll l, r;
struct task { 
    ll cnt, sumq, sum;
    task() {cnt = -1; sumq = sum = 0;} 
    //cnt 个数 sumq 平方和 sum和 
    //(a+b)^2=a^2+b^2+2ab
}f[23][23][23];

void init() {
    for(int i = 0; i <= 22; ++i) {
        for(int j = 0; j <= 22; ++j) {
            for(int k = 0; k <= 22; ++k) {
                f[i][j][k].cnt = -1;
                f[i][j][k].sumq = f[i][j][k].sum = 0;
            }
        }
    }
}

task dfs(int pos, bool done, ll sum, ll v) {
    // pos位 done判定上界 sum和对7的mod, v mod 7的值 
    if(!pos) {
        task tmp;
        tmp.cnt = sum && v;
        tmp.sum = tmp.sumq = 0;
        return tmp;
    }
    if(!done && f[pos][sum][v].cnt != -1) return f[pos][sum][v];
    ll ed = done ? num[pos] : 9; task res;
    res.cnt = 0;
    for(ll i = 0; i <= ed; ++i) {
        if(i == 7) continue;
        task tmp = dfs(pos - 1, done && (i == ed), (sum + i) % 7, (v * 10ll + i) % 7);
        res.cnt += tmp.cnt;
        res.cnt %= mod; 
        res.sum += tmp.sum + ((po[pos] * i) % mod * tmp.cnt) % mod;
        res.sum %= mod;
        res.sumq += tmp.sumq; res.sumq %= mod;
        res.sumq += (po[pos]*i%mod) * (po[pos]*i%mod) % mod * tmp.cnt % mod; res.sumq %= mod;
        res.sumq += 2ll * (po[pos]*i) % mod * tmp.sum % mod; res.sumq %= mod;
    }
    if(done) return res;
    return f[pos][sum][v] = res;
}

ll count(ll x) {
    init();
    cnt = 0;
    while(x) num[++cnt] = x % 10, x /= 10;
    return dfs(cnt, 1, 0, 0).sumq;
}

int main() {
    int T;
    po[1] = 1;
    for(int i = 2; i <= 22; ++i) po[i] = po[i - 1] * 10ll % mod;
    cin >> T;
    while(T--) {
        cin >> l >> r;
        cout << (count(r) - count(l - 1) + mod) % mod << endl;
    }
    return 0;
}