1 条题解

  • 0
    @ 2023-12-6 21:25:33
    #include <bits/stdc++.h>
    using namespace std;
    const long long MOD = 1e9 + 7;
    int T, a[22];
    long long l, r, f[22], ten[22], sum[22];
    bool vis[22];
    
    long long dfs(int p, bool limit) {
        if (p < 0) return 0;
        if (!limit && vis[p])
            return f[p];
        long long res = 0;
        int up = limit ? a[p] : 9;
        for (int i = 0; i <= up; i++) {
            res = (res + dfs(p-1, limit && i==up)) % MOD;
            if (limit && i==up)
                res = (res + i * (sum[p] + 1) % MOD) % MOD;
            else
                res = (res + i * ten[p] % MOD) % MOD;
        }
        if (!limit)
            vis[p] = true, f[p] = res;
        return res;
    }
    
    long long cal(long long num) {
        memset(vis, 0, sizeof vis);
        long long x = 1;
        for (int i = 0; i <= 18; i++, x *= 10) {
            sum[i] = num % x % MOD;
        }
        int p = 0;
        while (num) {
            a[p++] = num % 10;
            num /= 10;
        }
        return dfs(p-1, 1);
    }
    
    void init() {
        ten[0] = 1;
        for (int i = 1; i <= 20; i++)
            ten[i] = ten[i-1] * 10 % MOD;
    }
    
    int main() {
        init();
        scanf("%d", &T);
        while (T--) {
            scanf("%lld%lld", &l, &r);
            printf("%lld\n", (cal(r) - cal(l-1) + MOD) % MOD);
        }
        return 0;
    }
    
    • 1

    信息

    ID
    17
    时间
    1000ms
    内存
    256MiB
    难度
    (无)
    标签
    (无)
    递交数
    0
    已通过
    0
    上传者