题目描述
给你两个数字字符串 num1
和 num2
,以及两个整数 max_sum
和 min_sum
。如果一个整数 x
满足以下条件,我们称它是一个好整数:
num1 <= x <= num2
min_sum <= digit_sum(x) <= max_sum
请你返回好整数的数目。答案可能很大,请返回答案对 10^9 + 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 <= 10^22
1 <= min_sum <= max_sum <= 400
算法
(数位统计) $O(LS)$
- 预处理数组 $f(i, j)$ 表示长度为 $i$ 的数字串,组成数字和不超过 $j$ 的方案数。
- 初始时 $f(0, j) = 1$,表示长度为 $0$ 的情况,只有不填一种方案。其余为 $0$ 待定。
- 转移时,$f(i, 0) = 1$,对于 $f(i, j)$,如果 $j \ge 10$,则转移 $f(i, j) = f(i, j - 1) + (f(i - 1, j) - f(i - 1, j - 10))$。$f(i, j - 1)$ 是状态定义的自然含义,$f(i - 1, j) - f(i - 1, j - 10)$ 表示是可以从 $i-1$ 长度,数字和在区间 $[j - 9, j]$ 的场景下转移过来(对应当前位填 $0$ 到 $9$)。如果 $j < 10$,则就无需再减 $f(i - 1, j - 10)$。
- 令 $g(i, j) = \sum_{k=0}^{j} f(i, k)$,即 $f(i, j)$ 在第二维的前缀和,用于后续的数位统计。
- 题目要求的是求出数字区间 $[num1, num2]$ 在数字和区间 $[minsum, maxsum]$ 的答案,可以通过 $[0, num2][0, maxsum]$ 减去 $[0, num2][0, minsum - 1]$ 和 $[0, num1][0, maxsum]$,再加回 $[0, num1][0, minsum - 1]$ 得到结果,另外单独判断 $num1$ 是否符合条件。
- 假设当前求的是 $[0, n]$ 组成和不超过 $m$ 的数字个数,可以从最高位开始往下遍历。假设当前位数字为 $x$,除这一位之外剩余 $l$ 位尚未确定,当前数字和最大为 $sum$,则当前位可以选填 $j \in [0, x - 1]$,当前位之后的数字则可以随意填,所以答案累加 $f(l, sum) + f(l, sum - 1) + \dots + f(l, sum - x + 1)$,此时可以直接用 $g(l, sum) - g(l, sum - x)$ 替代枚举。
- 累加完答案后,当前位可以设置为 $x$,$sum$ 减去 $x$,然后处理下一位。如果 $sum < 0$,则直接结束。
- 最后,如果 $sum \ge 0$,则说明 $n$ 这个数字是合法的,答案自加 $1$ 后返回。
时间复杂度
- 预处理的时间复杂度为 $O(LS)$,其中 $L$ 为数字的最大长度,$S$ 为最大的数字和。
- 求解的时间复杂度为 $O(L)$。
- 故总时间复杂度为 $O(LS)$。
空间复杂度
- 需要 $O(LS)$ 的额外空间存储预处理数组。
C++ 代码
#define LL long long
const int mod = 1000000007;
const int L = 30, S = 410;
class Solution {
private:
int f[L][S], g[L][S];
void init(int n, int m) {
f[0][0] = g[0][0] = 1;
for (int j = 1; j <= m; j++) {
f[0][j] = 1;
g[0][j] = (g[0][j - 1] + f[0][j]) % mod;
}
for (int i = 1; i < n; i++) {
f[i][0] = g[i][0] = 1;
for (int j = 1; j <= m; j++) {
f[i][j] = (f[i][j - 1] + f[i - 1][j]) % mod;
if (j >= 10)
f[i][j] = (f[i][j] - f[i - 1][j - 10]) % mod;
g[i][j] = (g[i][j - 1] + f[i][j]) % mod;
}
}
}
int solve(string num, int sum) {
const int n = num.size();
int res = 0;
for (int i = 0; i < n; i++) {
int x = num[i] - '0';
res = (res + g[n - i - 1][sum]) % mod;
if (sum >= x)
res = (res - g[n - i - 1][sum - x]) % mod;
sum -= x;
if (sum < 0)
return res;
}
return res + 1;
}
public:
int count(string num1, string num2, int min_sum, int max_sum) {
init(num2.size(), max_sum);
int ans = 0;
ans = (ans + solve(num2, max_sum)) % mod;
ans = (ans - solve(num2, min_sum - 1)) % mod;
ans = (ans - solve(num1, max_sum)) % mod;
ans = (ans + solve(num1, min_sum - 1)) % mod;
int tot = 0;
for (char c : num1)
tot += c - '0';
if (min_sum <= tot && tot <= max_sum)
++ans;
return (ans + mod) % mod;
}
};