题目描述

注释版，仅记录。

算法1

C++ 代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

typedef long long LL;

const int N=20,P=1e9+7;

//调试长代码要先通篇看一遍

struct F{
    int s0,s1,s2;
}f[N][10][7][7];    //a是数值大小mod7，b是各位数字之和mod7；
                    //s0是数的个数，s1是各位数字之和，s2是各位数字的平方和。

int power7[N],power9[N];

int mod(LL x,int y) //取模运算
{
    return (x%y + y) %y;
}

void init()
{
    for (int i = 0; i <= 9; i ++ )
    {
        if (i == 7) continue;
        auto& v = f[1][i][i % 7][i % 7];
        v.s0 ++, v.s1 += i, v.s2 += i * i;
    }

    LL power = 10;      //保证power=10^(i-1)；
    for (int i = 2; i < N; i ++, power *= 10)
        for (int j = 0; j <= 9; j ++ )
        {
            if (j == 7) continue;
            for (int a = 0; a < 7; a ++ )
                for (int b = 0; b < 7; b ++ )
                    for (int k = 0; k <= 9; k ++ )
                    {
                        if (k == 7) continue;
                        auto &v1 = f[i][j][a][b], &v2 = f[i - 1][k][mod(a - j * power, 7)][mod(b - j, 7)];
                        v1.s0 = mod(v1.s0 + v2.s0, P);
                        v1.s1 = mod(v1.s1 + v2.s1 + j * (power % P) % P * v2.s0, P);
                        //greg的推导公式：
                        // jA1 + jA2 + ... + jAt
                        // = (j * 10 ^ (i - 1) + A1) + ...  // // think of f[i][j]
                        // = j * 10 ^ (i - 1) * t + (A1 + A2 + ... + At)
                        v1.s2 = mod(v1.s2 + j * j * (power % P) % P * (power % P) % P * v2.s0 + v2.s2 + 2 * j * power % P * v2.s1, P);
                        //同样是greg大佬的推导公式：
                        // (jA1) ^ 2 + (jA2) ^ 2 + ... + (jAt) ^ 2
                        // = (j * 10 ^ (i - 1) + A1) ^ 2 + ...
                        // = (j * j * 10 ^ (i - 1) * 10 ^ (i - 1) + 2 * j * 10 ^ (i - 1) * A1 + A1 * A1) + ...
                        // = (j * j * 10 ^ (i - 1) * 10 ^ (i - 1) * t + 
                        //    2 * j * 10 ^ (i - 1) * (A1 + A2 + ... + At) + 
                        //    (A1 * A1 + A2 * A2 + ... + At * At)
                    }

        }

    power7[0] = 1;  //power mod 7 ，防止超LL；
    for (int i = 1; i < N; i ++ ) power7[i] = power7[i - 1] * 10 % 7;

    power9[0] = 1;  //power mod P ，防止超LL；
    for (int i = 1; i < N; i ++ ) power9[i] = power9[i - 1] * 10ll % P;
}


//求mod7!=a,mod7!=b下的和，即满足第2，3个条件的值。
F get(int i, int j, int a, int b)
{
    int s0 = 0, s1 = 0, s2 = 0;
    for (int x = 0; x < 7; x ++ )
        for (int y = 0; y < 7; y ++ )
            if (x != a && y != b)
            {
                auto v = f[i][j][x][y];
                s0 = (s0 + v.s0) % P;
                s1 = (s1 + v.s1) % P;
                s2 = (s2 + v.s2) % P;
            }
    return {s0, s1, s2};
}




int dp(LL n)
{
    if (!n) return 0;

    LL backup_n = n % P;
    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0;
    LL last_a = 0, last_b = 0;
    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for (int j = 0; j < x; j ++ )
        {
            if (j == 7) continue;
            //-last_a这种在余数运算中很常见，记录全部数位mod7为0，前半部分mod7为la时，后面的余数是多少。
            int a = mod(-last_a * power7[i + 1], 7);
            int b = mod(-last_b, 7);
            auto v = get(i + 1, j, a, b);
            res = mod(
                res + 
                (last_a % P) * (last_a % P) % P * power9[i + 1] % P * power9[i + 1] % P * v.s0 % P + 
                v.s2 + 
                2 * last_a % P * power9[i + 1] % P * v.s1,
            P);
        }

        if (x == 7) break;
        last_a = last_a * 10 + x;
        last_b += x;

        if (!i && last_a % 7 && last_b % 7) res = (res + backup_n * backup_n) % P;
    }

    return res;
}


int main()
{
    int T;
    cin>>T;

    init();

    while(T--)
    {
        LL l,r;
        cin>>l>>r;
        cout<<mod(dp(r)-dp(l-1),P)<<endl;
    }

    return 0;
}