【Leetcode】2719. 统计整数数目

题目

2719. 统计整数数目

给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：
num1 <= x <= num2
min_sum <= digit_sum(x) <= max_sum.
请你返回好整数的数目。答案可能很大，请返回答案对 109 + 7 取余后的结果。
注意，digit_sum(x) 表示 x 各位数字之和。

示例一：
输入：num1 = “1”, num2 = “12”, min_num = 1, max_num = 8
输出：11
解释：总共有 11 个整数的数位和在 1 到 8 之间，分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。

示例二：
输入：num1 = “1”, num2 = “5”, min_num = 1, max_num = 5
输出：5
解释：数位和在 1 到 5 之间的 5 个整数分别为 1,2,3,4 和 5 。所以我们返回 5 。

提示：
1 <= num1 <= num2 <= 1022
1 <= min_sum <= max_sum <= 400

思路

这道题可以使用数位dp来解决，dp[i][j] 表示 i个数位之和小于等于j的情况数量，逐位递推即可，具体看这个 推理的过程
两种数位 DP 模板，附题单（Python/Java/C++/Go）

代码

constexpr int64_t mod = 1000000007;
constexpr int N = 22+1, M = N*9;
int64_t dp[N+1][M+1];
auto rb = [](auto x){return (x % mod + mod) % mod;};
auto _ = []{
    fill_n(dp[0], M+1, 1);
    for(int i = 1; i <= N; ++i){
        int64_t presum{};
        for(int j = 0; j <= M; ++j){
            presum += j >= 10 ? rb(dp[i-1][j] - dp[i-1][j-10]) : dp[i-1][j];
            dp[i][j] = presum = rb(presum);
        }
    }
    return 0;
}();
        
class Solution {
public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        num1.back()--;
        min_sum--;
        max_sum = min(max_sum, M);
        min_sum = min(min_sum, M);
        for(int i = num1.size()-1; i >= 0 && num1[i] == '0'-1; --num1[--i]) num1[i] = '9';
        
        int n = num2.size();
        auto solve = [&](string num, int max_sum){
            int n = num.size(), sum = max_sum;
            int64_t ans = 0;
            for(int i = 0; i < n && sum >= 0; ++i){
                int x = num[i] - '0';
                for(int j = 0; j < x && j <= sum; ++j)
                    ans += dp[n-i-1][sum-j];
                sum -= x;
            }
            return rb(ans + (sum >= 0));
        };
        return rb(solve(num2, max_sum) - solve(num2, min_sum) - solve(num1, max_sum) + solve(num1, min_sum));
    }
};