题解：P11557 [ROIR 2016 Day 2] 有趣数字

· · 题解

PS：本人是一个初中的蒟蒻，如有问题，欢迎指出。

1. 确定算法

首先，查看算法标签 看一眼要求，一个区间内的符合要求的数，那么就可以判断出用数位 DP。基于前缀和思想，用 \left[ 0, R \right] 区间内符合要求的数减去 \left[ 0, L - 1 \right] 区间内符合要求的数得到答案。

2. 解决难点

本题最大的难点在数据范围，第一眼过去，1 \leq L \leq R \leq 10^{100}。

BYD 这破题还要高精。

但再仔细查看可以看到需要取余，那么直接在计算答案的地方加上取余即可。最难的地方在输入，这里可以用字符串，但别忘了要加一点点代码实现左范围减去一。

除此之外，由于我们在计算过程中取余，在计算答案时可能会被诡异 BUG 弄得一脸茫然（输出负数），这是因为取余后可能右区间比左区间小，所以最后输出答案时还需要加上取余数再取余。

最后，使用数位 DP 的板子稍加修改，即可通过。

附上 AC 代码：

#include <string>
#include <iostream>

#define Code using
#define by namespace 
#define Txy120607 std;

Code by Txy120607

#define int long long
const int N = 120, P = 1e9 + 7;  // P 为取余数 
int num[N]; int f[N][N];

// 初始化 DP 数组
void init() { 
    for (int i = 0; i <= 9; i++)
        f[1][i] = 1;
    for (int i = 2; i < N; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = j; k <= 9; k++) {
                f[i][j] += f[i - 1][k]; // f[i][j] 计算方式
            }
        }
    }
}

int solve(string e) {
    int cnt = e.size();
    for (int i = cnt - 1; i >= 0; i--) { // 反转字符串
        num[cnt - i] = e[i] - '0';
    }
    int ans = 0, l = 0;
    for (int i = cnt; i >= 1; --i) { // 统计符合条件的数的个数
        int n = num[i];
        for (int j = l; j < n; j++) {
            ans += f[i][j] % P;
            ans %= P;
        }
        if (n < l) break; // 剪枝
        l = n;
        if (i == 1) ans++; // 最后一位的处理
        ans %= P; // 取余
    }
    return ans;
}

signed main() {
    init();
    string l, r;
    cin >> l >> r;

    int i;
    // 实现字符串 l - 1 的效果
    for (i = l.size() - 1; l[i] == '0'; i--); // 从右往左找第一个非零数字
    l[i] -= 1; // 找到的非零数字减去 1
    i++;
    for (; i < l.size(); i++) l[i] = '9'; // 剩余位数都设为 9

    // 输出 (r - l + P) % P，保证非负结果
    cout << (solve(r) - solve(l) + P) % P; 

    return 0;
}