Luobuyu's Blog

0%

2719. 统计整数数目

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 4.2k 阅读时长 ≈ 4 分钟
数位dp，但是要注意long long范围

2719.统计整数数目

题目描述：

给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：

  • num1 <= x <= num2
  • min_sum <= digit_sum(x) <= max_sum.

请你返回好整数的数目。答案可能很大，请返回答案对 $10^9 + 7$ 取余后的结果。

注意，digit_sum(x) 表示 x 各位数字之和。

数据范围：

$1\le num1 \le num2 \le 10^{22}, 1\le min\_sum \le max\_sum \le 400$

题解：

统计数量，可以使用数位dp。

而且刚好分成两个前缀相减，solve(num2, min_sum, max_sum) - solve(num1 - 1, min_sum, max_sum)。

需要注意的是， $num1 - 1$ 。因为 $num1$ 最大为 $10^{22}$ 已经超出了 long long 范围。 $(2^{10})^7 \approx (10^3)^7 = 10^{21} \lt 10^{22}$ 但是， $2^{70}$ 已经超过 $2 ^ {64}$ 了。 $2^{64} \approx (10^3)^{6.4} \approx 10^{18}$ ，long long最大值在 $(10^{18}, 10^{19})$ 之间。

所以可以不减去solve(num1 - 1) 直接减去 solve(num1) 然后单独判断 num1 是否符合答案要求。

而且这个题目不用加 isLead，因为存在前导零对数位和没有影响，也就是 03,003,0003 和 3 是一样的。

模板如下，加不加 isLead，主要可以看下面两次调用 dfs 时 state 是否一样，不一样的话就需要加 isLead。例如 2827. 范围中美丽整数的数目 | Luobuyu’s Blog 中，如果循环中 $i = 0$ ，那么是会被加到 $diff$ 里面的，但是如果 $i = 0$ 是一个前导零就不应该加进去，因此这个题目就需要加上 isLead。

但是该题目就不需要，虽然加不加都一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// state针对不同的问题设置状态，可能有多个状态
// is_limit 表示是否收到上界的限制
// is_lead 表示是否存在前导零
int dfs(int step, int state, bool is_limit, bool is_lead)
{
    if (step == n)
        return !is_lead;
    // 只能记忆化非限制的，无限制，无前导零
    if (!is_limit && !is_lead && dp[step][val][diff] != -1)
        return dp[step][val][diff];
    int ans = 0;
    // 存在前导零的情况下可以跳过该位
    if (is_lead)
        ans = dfs(step + 1, state, false, true);
    int up = is_limit ? s[step] - '0' : 9;
    // 存在前导零，从1开始，不存在，从0开始。下一个一定不存在前导零。
    for (int i = is_lead; i <= up; ++i)
    {
        ans += dfs(step + 1, state, is_limit && i == up, false);
    }
    if (!is_limit && !is_lead)
        dp[step][state][diff] = ans;
    return ans;
}
dfs(0, 0, true, true);

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    const long long mod = 1e9 + 7;
    // solve <= num, digit <= max_sum
    // step 遍历到第几位，sum数位和，isLimit当前位是否受到上界限制，isLead是否存在前导零
    string s;
    int n;
    long long dp[23][220];
    int minx, maxx;
    int dfs(int step, int sum, bool isLimit, bool isLead)
    {
        if (sum > maxx)
            return 0;
        if (step == n)
            return !isLead && sum >= minx; // 不能是纯零
        if (!isLimit && !isLead && dp[step][sum] != -1)
            return dp[step][sum];
        long long ans = 0;
        if (isLead) // 这一位填 0
            ans = (ans + dfs(step + 1, sum, false, true)) % mod;
        int up = isLimit ? s[step] - '0' : 9;
        for (int i = isLead; i <= up; ++i) // 存在前导零的话，从1开始填，否则从0开始填。
        {
            ans = (ans + dfs(step + 1, sum + i, isLimit && (i == up), false)) % mod;
        }
        if (!isLimit && !isLead)
            dp[step][sum] = ans;
        return ans;
    }
    int solve(string upper, int min_sum, int max_sum)
    {
        memset(dp, -1, sizeof(dp));
        s = upper;
        n = s.length();
        minx = min_sum;
        maxx = max_sum;
        return dfs(0, 0, true, true);
    }
    int count(string num1, string num2, int min_sum, int max_sum)
    {
        long long ret1 = solve(num2, min_sum, max_sum);
        long long ret2 = solve(num1, min_sum, max_sum);
        int sum = 0;
        for (auto &ch : num1)
        {
            sum += ch - '0';
        }
        if (sum >= minx && sum <= maxx)
            ret2 -= 1;
        return (ret1 - ret2 + mod) % mod;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    const long long mod = 1e9 + 7;
    // solve <= num, digit <= max_sum
    // step 遍历到第几位，sum数位和，isLimit当前位是否受到上界限制，isLead是否存在前导零
    string s;
    int n;
    long long dp[23][220];
    int minx, maxx;
    int dfs(int step, int sum, bool isLimit)
    {
        if (sum > maxx)
            return 0;
        if (step == n)
            return sum >= minx; // 不能是纯零
        if (!isLimit && dp[step][sum] != -1)
            return dp[step][sum];
        long long ans = 0;
        int up = isLimit ? s[step] - '0' : 9;
        for (int i = 0; i <= up; ++i) // 存在前导零的话，从1开始填，否则从0开始填。
        {
            ans = (ans + dfs(step + 1, sum + i, isLimit && (i == up))) % mod;
        }
        if (!isLimit)
            dp[step][sum] = ans;
        return ans;
    }
    int solve(string upper, int min_sum, int max_sum)
    {
        memset(dp, -1, sizeof(dp));
        s = upper;
        n = s.length();
        minx = min_sum;
        maxx = max_sum;
        return dfs(0, 0, true);
    }
    int count(string num1, string num2, int min_sum, int max_sum)
    {
        long long ret1 = solve(num2, min_sum, max_sum);
        long long ret2 = solve(num1, min_sum, max_sum);
        int sum = 0;
        for (auto &ch : num1)
        {
            sum += ch - '0';
        }
        if (sum >= minx && sum <= maxx)
            ret2 -= 1;
        return (ret1 - ret2 + mod) % mod;
    }
};