思路

(数位DP)

其实我主要是来说bug会出在哪的。这道题一不小心，就会出些bug时间远超写代码时间的状况。
因为这道题的范围很恶心，随处都有可能超范围，所以一定要注意小括号和取模，而且有些地方得加，有些地方不能加，
我是因为没有及时加小括号，或者取模，然后超范围，bug改了几个小时，哎~
至于思路，略说一下，y总的课上已经讲的很清楚了。
还有就是一些小地方的写法上，我觉得通过枚举上一个状态在写的时候会稍微好写一些，也更易于理解。
还有就是可以直接表示出last_a,直接表示写起来也简洁不少。

其中f[i][j][a][b]表示:当前最高位是第i位，最高位数字是j，当前数本身mod7=a，当前数各位之和mod7=b
//把所有状态压缩起来
假设当最高位是j时，有t个数满足，则：
  (jA1)+(jA2)+(jA3)+...+(jAt)
= (j*10^{i-1})*t + (A1+A2+A3+...+At)
  (jA1)^2+(jA2)^2+(jA3)^2+...+(jAt)^2

= ((j*10^{i-1})^2)*t + 
  2*(j*10^{i-1})*(A1+A2+...+At) + 
  (A1^2+A2^2+...+At^2)

  我们要维护的就是t,s1,s2,而这些都在能推到f[i][j][a][b]的所有f[i-1][j'][a'][b']能找到
  所以各部分根据以上推导再累加求和就行

C++ 代码

#include <iostream>
#include <cstring>
#include <vector>

using namespace std ;

typedef long long LL ;

const LL P = 1000000007 , N = 20 ;

int mod(LL x , LL y = P)
{
    return (x % y + y ) % y;
}

struct F{
    int t,s1,s2 ;   //t表示有几个，s1表示：A1+A2+...+At，s2表示：A1^2+A2^2+...+At^2
}f[N][10][7][7] ;   
//f[i][j][a][b]:当前最高位是第i位，最高位数字是j，当前数本身mod7，当前数各位之和mod7

void init() //获得满足第一个条件
{
    for(int i = 0 ; i < 10 ; i++ )  
    {
        if( i == 7 )    continue ;
        auto &v = f[1][i][i%7][i%7];
        v.t ++;
        v.s1 += i ;
        v.s2 += i*i ;
    }

    LL power = 10 ;
    for(int i = 2; i < N ; i++ , power*=10)
        for(int j = 0 ; j < 10 ; j++ )  //当前位
        {
            if(j == 7)  continue ;
            for(int k = 0 ; k < 10 ; k++ )//上一位的最高位
            {
                if( k == 7 )    continue;
                for(int a = 0 ; a < 7 ; a++)    //上一位的a
                    for(int b = 0 ; b < 7 ; b++)    //上一位的b
                    {
                    /*
                      (jA1)+(jA2)+(jA3)+...+(jAt)
                    = (j*10^{i-1})*t + (A1+A2+A3+...+At)

                      (jA1)^2+(jA2)^2+(jA3)^2+...+(jAt)^2
                    = ((j*10^{i-1})^2)*t + 
                      2*(j*10^{i-1})*(A1+A2+...+At) + 
                      (A1^2+A2^2+...+At^2)
                    */
                        LL powj = j*power;  //j*10^{i-1}
                        auto &v1 = f[i][j][mod(a+powj , 7)][mod(b+j , 7)] , &v2 = f[i-1][k][a][b] ;
                        v1.t = mod(v1.t + v2.t);
                        v1.s1 = mod(v1.s1 + powj % P * v2.t  + v2.s1);
                        v1.s2 = mod(v1.s2 + 
                                    (powj % P) * (powj % P) % P * v2.t + 
                                    2 * powj % P * v2.s1 + 
                                    v2.s2);
                    }
            }
        }

}

F get(int n , int m , int a , int b)    //获取满足第二和第三个条件的
{
    int t = 0 , s1 = 0 , s2 = 0 ;
    for(int i = 0 ; i < 7 ; i++)
        for(int j = 0 ; j < 7 ; j++ )
        {
            if(i == a || j == b)    continue ;
            auto &v = f[n][m][i][j] ;    
            t = mod(t + v.t);   //有多少个
            s1 = mod(s1 + v.s1);    //和
            s2 = mod(s2 + v.s2);    //平方和
        }

    return {t , s1 , s2};
}


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

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

    LL res = 0 ;
    LL last_a = 0 , last_b = 0 ;//前几位的数，前几位的和

    LL power = 1 ; 
    for(int i = 0 ; i < nums.size()-1 ; i++)  //10^i
        power *= 10 ;

    for(int i = nums.size()-1 ; i >= 0 ; i-- , power/=10)
    {
        int x = nums[i] ;
        for(int j = 0 ; j < x ; j++ )   //当前位
        {
            if( j == 7 )    continue ;
            int a = mod(-last_a , 7);   //之前的余数不能是a
            int b = mod(-last_b , 7);   //余数不能是b

            auto v = get(i+1 , j , a , b) ;    //获得最高位是i+1位，当前位是j，且不能是a，b的所有情况

            /*
              (jA1)+(jA2)+(jA3)+...+(jAt)
            = (j*10^{i-1})*t + (A1+A2+A3+...+At)

              (jA1)^2+(jA2)^2+(jA3)^2+...+(jAt)^2
            = ((j*10^{i-1})^2)*t + 
              2*(j*10^{i-1})*(A1+A2+...+At) + 
              (A1^2+A2^2+...+At^2)
            */

            res = mod(res + 
                      (last_a % P) * (last_a % P) % P * v.t % P + 
                      2 * last_a % P * v.s1 % P + v.s2
                     );
        }

        if( x == 7 )    break;
        last_a = last_a + x*power; //前面的数
        last_b = last_b + x;   //前面的各位数之和

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

    }

    return res ;
}

int main()
{
    init() ;
    int T ;
    cin >> T ;
    while( T -- )
    {
        LL l , r ; 
        cin >> l >> r ; 
        cout << mod(dp(r) - dp(l-1)) << endl;
    }
    return 0;
}