M2906.构造乘积矩阵

prefix sum, https://leetcode.cn/problems/construct-product-matrix/

给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：

对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。

返回 grid 的乘积矩阵。

示例 1：

输入：grid = [[1,2],[3,4]]
输出：[[24,12],[8,6]]
解释：p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
所以答案是 [[24,12],[8,6]] 。

示例 2：

输入：grid = [[12345],[2],[1]]
输出：[[2],[0],[0]]
解释：p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[0][1] = 0
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[0][2] = 0
所以答案是 [[2],[0],[0]] 。

提示：

1 <= n == grid.length <= 10^5
1 <= m == grid[i].length <= 10^5
2 <= n * m <= 10^5
1 <= grid[i][j] <= 10^9

这道题要求计算一个乘积矩阵 $p$ ，其中 $p [i] [j]$ 是原矩阵 grid 中除 grid[i][j] 以外所有元素的乘积，结果对 $12345$ 取余。

由于 $12345$ 不是质数（ $12345 = 3 \times 5 \times 823$ ），且 grid 中的元素可能包含 $12345$ 的因子甚至就是其倍数，因此我们不能使用“总乘积除以当前元素”的方法（因为除数可能没有模逆元）。

解决此类问题的标准做法是利用前缀积和后缀积。我们可以将二维矩阵看作一个扁平化的一维序列，计算每个位置左侧所有元素的积和右侧所有元素的积。

算法步骤：

初始化：创建一个与 grid 大小相同的矩阵 ans 用于存放结果。
前缀积遍历：
- 遍历矩阵（从左到右，从上到下）。
- 使用变量 curr 记录当前位置之前所有元素的乘积（初始为 1）。
- 将 ans[i][j] 设置为当前的 curr。
- 更新 curr，将其乘以 grid[i][j] 并对 $12345$ 取模。
后缀积遍历：
- 逆向遍历矩阵（从右到左，从下到上）。
- 使用变量 curr 记录当前位置之后所有元素的乘积（重新初始化为 1）。
- 将 ans[i][j] 乘上当前的 curr 并对 $12345$ 取模。
- 更新 curr，将其乘以 grid[i][j] 并对 $12345$ 取模。
返回结果。

Python 代码实现：

python

from typing import List

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        m = len(grid[0])
        MOD = 12345
        
        # ans 矩阵首先用来存储前缀积
        ans = [[0] * m for _ in range(n)]
        
        curr = 1
        # 正向遍历：计算每个位置之前所有元素的乘积
        for i in range(n):
            for j in range(m):
                ans[i][j] = curr
                # 更新前缀积，及时取模防止数值过大
                curr = (curr * grid[i][j]) % MOD
        
        curr = 1
        # 逆向遍历：计算每个位置之后所有元素的乘积，并与前缀积相乘
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                # 此时 ans[i][j] 是前缀积，curr 是后缀积
                ans[i][j] = (ans[i][j] * curr) % MOD
                # 更新后缀积
                curr = (curr * grid[i][j]) % MOD
                
        return ans

复杂度分析：

时间复杂度： $O (n \times m)$ 。我们需要遍历矩阵两次（一次前向，一次后向），总操作次数与矩阵元素个数成线性关系。
空间复杂度： $O (1)$ 。除了存储结果所需的 ans 矩阵外，只使用了常数个额外变量（如果不算返回的矩阵，空间复杂度为 $O (1)$ ；算上则是 $O (n \times m)$ ）。

关键点总结：

前缀积+后缀积是处理“除自身以外的所有元素之积”类问题的经典技巧，它规避了除法运算和 $0$ 的处理。
题目给出的模数 $12345$ 较小，中间计算虽然会超过这个值，但在 Python 中会自动处理大整数，且通过及时取模可保证效率。

M2906.构造乘积矩阵 ​

M2906.构造乘积矩阵