题目描述

某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [1, k] 之间，且数组中的数字都没有前导零。

给你字符串 s 和整数 k。可能会有多种不同的数组恢复结果。

按照上述程序，请你返回所有可能输出字符串 s 的数组方案数。

由于数组方案数可能会很大，请你返回它对 10^9 + 7 取余 后的结果。

样例

输入：s = "1000", k = 10000
输出：1
解释：唯一一种可能的数组方案是 [1000]

输入：s = "1000", k = 10
输出：0
解释：不存在任何数组方案满足所有整数都 >= 1 且 <= 10 同时输出结果为 s。

输入：s = "1317", k = 2000
输出：8
解释：可行的数组方案为
[1317]、[131,7]、[13,17]、[1,317]、[13,1,7]、[1,31,7]、[1,3,17] 和 [1,3,1,7]。

输入：s = "2020", k = 30
输出：1
解释：唯一可能的数组方案是 [20,20]。
[2020] 不是可行的数组方案，原因是 2020 > 30。
[2,020] 也不是可行的数组方案，因为 020 含有前导零。

输入：s = "1234567890", k = 90
输出：34

限制

• 1 <= s.length <= 10^5
• s 只包含数字且不包含前导零。
• 1 <= k <= 10^9

算法

(动态规划) $O(n \log_{10} k)$

1. 设状态 $f(i)$ 表示前 $i$ 个数字的合法划分方案，这里的下标从 1 开始。
2. 初始值 $f(0) = 1$，其余为 0。
3. 转移时，如果子串 [j + 1, i] 转换为数字后在范围 [1, k] 中，则转移 $f(i) = f(i) + f(j)$。
4. 最终答案为 $f(n)$。

时间复杂度

• 状态数为 $O(n)$，转移时，$j$ 不会小于 $i - \log_{10} k - 1$，所以总时间复杂度为 $O(n \log_{10} k)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储状态。

C++ 代码

class Solution {
public:
    #define LL long long
    int numberOfArrays(string s, int k) {
        const int mod = 1000000007;
        int n = s.size();
        vector<int> f(n + 1, 0);
        f[0] = 1;

        for (int i = 1; i <= n; i++) {
            LL cur = 0, p = 1;
            for (int j = i - 1; j >= 0 && p <= k; j--, p *= 10) {
                cur += (s[j] - '0') * p;
                if (cur <= k && s[j] != '0')
                    f[i] = (f[i] + f[j]) % mod;
            }
        }

        return f[n];
    }
};