M3756.连接非零数字并乘以其数字和 II

前缀和，https://leetcode.cn/problems/concatenate-non-zero-digits-and-multiply-by-sum-ii/

给你一个长度为 m 的字符串 s，其中仅包含数字。另给你一个二维整数数组 queries，其中 queries[i] = [li, ri]。

对于每个 queries[i]，提取子串 s[li..ri]，然后执行以下操作：

将子串中所有 非零数字 按照原始顺序连接起来，形成一个新的整数 x。如果没有非零数字，则 x = 0。
令 sum 为 x 中所有数字的 数字和 。答案为 x * sum。

返回一个整数数组 answer，其中 answer[i] 是第 i 个查询的答案。

由于答案可能非常大，请返回其对 109 + 7 取余数的结果。

子串是字符串中的一个连续、非空字符序列。

示例 1：

输入： s = "10203004", queries = [[0,7],[1,3],[4,6]]

输出： [12340, 4, 9]

解释：

s[0..7] = "10203004"
- x = 1234
- sum = 1 + 2 + 3 + 4 = 10
- 因此，答案是 1234 * 10 = 12340。
s[1..3] = "020"
- x = 2
- sum = 2
- 因此，答案是 2 * 2 = 4。
s[4..6] = "300"
- x = 3
- sum = 3
- 因此，答案是 3 * 3 = 9。

示例 2：

输入： s = "1000", queries = [[0,3],[1,1]]

输出： [1, 0]

解释：

s[0..3] = "1000"
- x = 1
- sum = 1
- 因此，答案是 1 * 1 = 1。
s[1..1] = "0"
- x = 0
- sum = 0
- 因此，答案是 0 * 0 = 0。

示例 3：

输入： s = "9876543210", queries = [[0,9]]

输出： [444444137]

解释：

s[0..9] = "9876543210"
- x = 987654321
- sum = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45
- 因此，答案是 987654321 * 45 = 44444444445。
- 返回结果为 44444444445 mod (109 + 7) = 444444137。

提示：

1 <= m == s.length <= 10^5
s 仅由数字组成。
1 <= queries.length <= 10^5
queries[i] = [li, ri]
0 <= li <= ri < m

方法分析

对于每个查询区间 $[l, r]$ ，我们需要求出非零数字拼接而成的整数 $x$ 以及这些数字的和 $sum$ ，并求 $x \times sum (\mod 10^{9} + 7)$ 。

数字和（sum）的计算：
- 我们可以使用前缀和来快速求得。令 $P [i] = \sum_{j = 0}^{i - 1} s [j]$ 。
- 对于区间 $[l, r]$ ，其所有数字之和即为 $P [r + 1] - P [l]$ 。这一步可以在 $O (1)$ 时间内完成。
拼接整数 $x (\mod 10^{9} + 7)$ 的计算：
- 设区间 $[l, r]$ 中的非零数字按原顺序为 $d_{1}, d_{2}, \dots, d_{k}$ （共 $k$ 个）。
- 那么拼接而成的整数 $x = \sum_{j = 1}^{k} d_{j} \cdot 10^{k - j}$ 。
- 引入前缀非零数字个数 $C [i]$ ，表示 $s [0. . i - 1]$ 中非零数字的个数。
- 对于在索引 $p \in [l, r]$ 的非零数字 $s [p]$ ，它在整个字符串 $s$ 中是第 $C [p + 1]$ 个非零数字。
- 这个数字在子串中的右侧非零数字个数为 $C [r + 1] - C [p + 1]$ ，因此它对 $x$ 的贡献是 $s [p] \cdot 10^{C [r + 1] - C [p + 1]}$ 。
- 将所有的贡献相加，得到： $x = \sum_{p = l, s [p] \neq^{'} 0^{'}}^{r} s [p] \cdot 10^{C [r + 1] - C [p + 1]} = 10^{C [r + 1]} \sum_{p = l, s [p] \neq^{'} 0^{'}}^{r} s [p] \cdot 10^{- C [p + 1]}$
- 我们可以借助乘法逆元，预计算 $10^{- i} (\mod 10^{9} + 7)$ 的值。
- 定义前缀加权和 $S [i] = \sum_{p = 0}^{i - 1} [s [p] \neq^{'} 0^{'}] \cdot s [p] \cdot 10^{- C [p + 1]} (\mod 10^{9} + 7)$ 。
- 那么，区间 $[l, r]$ 的非零数字拼接值 $x$ 满足： $x \equiv (S [r + 1] - S [l]) \cdot 10^{C [r + 1]} (\mod 10^{9} + 7)$
- 该计算也可以在 $O (1)$ 时间内完成。

Python 代码实现

python

from typing import List

class Solution:
    def sumAndMultiply(self, s: str, queries: List[List[int]]) -> List[int]:
        MOD = 10**9 + 7
        m = len(s)
        
        # 将字符转换为数字列表
        digits = [int(c) for c in s]
        
        # 预计算 10 的幂和 10 的逆元的幂
        pow10 = [1] * (m + 1)
        inv10 = [1] * (m + 1)
        inv10_val = pow(10, MOD - 2, MOD)
        for i in range(1, m + 1):
            pow10[i] = (pow10[i-1] * 10) % MOD
            inv10[i] = (inv10[i-1] * inv10_val) % MOD
            
        C = [0] * (m + 1) # 非零数字计数的前缀和
        P = [0] * (m + 1) # 数字和的前缀和
        S = [0] * (m + 1) # 加权非零数字前缀和
        
        c_acc = 0
        p_acc = 0
        s_acc = 0
        for i, d in enumerate(digits):
            if d != 0:
                c_acc += 1
                s_acc = (s_acc + d * inv10[c_acc]) % MOD
            p_acc += d
            C[i+1] = c_acc
            P[i+1] = p_acc
            S[i+1] = s_acc
            
        ans = []
        for l, r in queries:
            digit_sum = P[r+1] - P[l]
            # 如果区间内没有非零数字，x = 0，答案为 0
            if digit_sum == 0:
                ans.append(0)
                continue
            
            # 计算拼接出的 x
            x = (S[r+1] - S[l]) * pow10[C[r+1]] % MOD
            ans.append((x * digit_sum) % MOD)
            
        return ans

复杂度分析

时间复杂度：
- 预处理：生成前缀和数组 C、P 和 S 以及幂数组需要 $O (m)$ 的时间。
- 查询：每次查询只需要进行常数次基本运算，因此单次查询时间复杂度为 $O (1)$ 。
- 总时间复杂度为 $O (m + q)$ ，其中 $q$ 为 queries 的长度。对于 $10^{5}$ 的数据规模，可以在 0.2 秒内运行完毕。
空间复杂度：
- 需要存储长度为 $m + 1$ 的前缀数组 C、P、S、pow10 和 inv10。
- 空间复杂度为 $O (m)$ 。

M3756.连接非零数字并乘以其数字和 II ​

M3756.连接非零数字并乘以其数字和 II