#include<bits/stdc++.h>
using namespace std;

long long f[20][10];
const int N = 1e9 + 7;

void init() {
    for (int j = 0;j <= 9;j++) {
        f[1][j] = j;
    }
    for (int i = 2;i <= 19;i++) {
        for (int j = 0;j <= 9;j++) {
            for (int cnt = 0;cnt <= 9;cnt++) {
                f[i][j] += f[i - 1][cnt];
            }
            f[i][j] += j * pow(10, i - 1);
            f[i][j] %= N;
        }
    }
    return;
}

long long fs(long long a) {
    int k[30], top = 0;
    memset(k, 0, sizeof(k));

    while (a > 0) {
        k[++top] = a % 10;
        a /= 10;
    }

    long long sum = 0;
    int hel = 0;
    for (int i = top; i >= 1;i--) {
        for (int j = 0;j < k[i];j++) {
            sum += f[i][j];
            sum %= N;
        }
        hel += k[i + 1];//属于(6+5+4+3)那一部分
        sum += hel * k[i] * pow(10, i - 1);
        sum %= N;
    }
    for (int i = 1;i <= top;i++) {
        sum += k[i];
    }

    return sum%N;
}
int main() {
    int t;
    scanf("%d", &t);
    init();
    for (int i = 1;i <= t;i++) {
        long long l, r;
        scanf("%lld%lld", &l, &r);
        printf("%lld\n", (fs(r)-fs(l-1))%N);
    }
    return 0;
}

我这里的f[i][j]表示以j为最高位的所有i位数的数字和的总和

例如f[3][2]表示200~299的数字和之和。

列出状态转移方程为 f[i][j] = f[i-1][0]+...+f[i-1][9]+j * 10^(i-1) 表示从000…00~999…99（i-1位）共10^(i-1)个数同时加了j

求0~某数的数字和也从最高位开始加起

例如求654321~0

f[6][0~5]表示从000000到599999

f[5][0~4]表示从00000到49999，加上 50000 * 6， 表示从600000到649999。

f[4][0~3]表示从0000到3999,加上 （6+5）* 4000表示从650000 到653999。

f[3][0~2]表示从000到299,加上 （6+5+4）* 300表示从654000 到654299。

f[2][0~1]表示从00到19,加上(6+5+4+3) * 20表示从654300到654319。

f[1][0]表示0，加上(6+5+4+3+2) * 1 表示654320。

最后剩下654321，sum加上6+5+4+3+2+1即可。

为什么会出错啊，65分....

求大佬解答。Orz