55pts求助awa
查看原帖
55pts求助awa
372729
创造君楼主2023/8/27 19:45
#include <bits/stdc++.h>

const int MAX_SIZE = 18;

const long long MOD = 1e9 + 7;

int num[MAX_SIZE + 5];
long long f[MAX_SIZE + 5][(MAX_SIZE + 5) * 10];

long long dp(int pos, int sum, bool flag) {
    if (pos == 1) {
        return sum;
    }
    if (flag == false && f[pos][sum] != -1) {
        return f[pos][sum];
    }
    int res = 0, maxNum = flag ? num[pos - 1] : 9;
    for (int i = 0; i <= maxNum; i++) {
        res += dp(pos - 1, sum + i, flag && (i == num[pos - 1]));
        res %= MOD;
    }
    if (flag == false) {
        f[pos][sum] = res;
    }
    return res;
}

long long solve(int x) {
    memset(num, 0, sizeof(num));
    for (int i = 0; i < MAX_SIZE + 5; i++) {
        for (int j = 0; j < (MAX_SIZE + 5) * 10; j++) {
            f[i][j] = -1;
        }
    }
    int len = 0;
    while (x) {
        len++;
        num[len] = x % 10;
        x /= 10;
    }
    return dp(len + 1, 0, true);
}

int main() {
    int t;
    std::cin >> t;
    for (int i = 1; i <= t; i++) {
        int l, r;
        std::cin >> l >> r;
        std::cout << std::abs(solve(r) - solve(l - 1)) % MOD << std::endl;
    }
    return 0;
}
2023/8/27 19:45
加载中...