题目

给你一个下标从 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

解题思路

一个直接的思路是先全乘，然后每个数除一下再取余，这里要考虑一下乘除和取余的数学性质，在数学和编程中，乘法和取余的关系是：

$$(a \times b) \pmod c = ((a \pmod c) \times (b \pmod c)) \pmod c$$ 但是取余运算对除法并不直接适用，在模 $c$ 的情况下，除以 $d$ 并不等同于普通的除法.

在模运算中，我们不直接做“除法”，而是寻找一个数字（记作 $d^{-1}$），使得：

$$d \times d^{-1} \equiv 1 \pmod c$$ 这个 $d^{-1}$ 就叫作 $d$ 模 $c$ 的逆元。你可以把它类比为数学里的“倒数”，但在模运算中它是一个整数。

正确的公式是：

$$(a \div d) \pmod c = (a \times d^{-1}) \pmod c$$

计算这个逆元常用的方法通常有两种：

费马小定理

如果 $c$ 是一个质数（这在算法题和密码学中非常常见，比如 $10^9+7$），那么：

$$d^{-1} \equiv d^{c-2} \pmod c$$

这意味着，除以 $d$ 等价于乘以 $d$ 的 $c-2$ 次方。

扩展欧几里得算法 (ExGCD)

如果 $c$ 不是质数，只要 $d$ 和 $c$ 互质（最大公约数为 1），就可以用 ExGCD 来算。

但是对于这道题的问题是：

模逆元不存在：这道题的模数是 12345，它不是质数（$12345 = 3 \times 5 \times 823$）。正如前面讨论的，如果 grid[i][j] 与 12345 不互质（比如 grid[i][j] 是 3 或 5 的倍数），除法在取余意义下就无解。
零值问题：如果 grid 中有一个元素对 12345 取余等于 0（如示例 2），total_prod % 12345 就会变成 0，你无法通过除以 0 来还原其他位置的乘积。

前缀积 + 后缀积

为了避开除法，我们可以利用“空间换时间”的策略，分别计算每个元素之前的所有元素乘积和之后的所有元素乘积。

我们将二维矩阵想象成一条线（拉平成一维），长度为 $L = n \times m$。

第一步：计算前缀积 (Prefix Product)

创建一个数组（或直接在结果矩阵 p 上操作），令 p[k] 等于前 $k-1$ 个元素的乘积。

p[0] = 1（第一个元素前面没有数，乘积单位元为 1）
p[1] = grid[0]
p[2] = grid[0] * grid[1]
以此类推：p[k] = (p[k-1] * grid[k-1]) % 12345

第二步：计算后缀积 (Suffix Product)

我们不需要额外的数组存后缀积，只需要一个变量 suffix 实时维护。

从最后一个元素开始往前走：

当前的 p[k] 已经是它前面的积了，我们把它乘以当前的 suffix，就得到了“前积 $\times$ 后积”，即“除了自己以外的积”。
更新 suffix：suffix = (suffix * grid[k]) % 12345。

具体算法流程

初始化一个 $n \times m$ 的矩阵 res。
从左上到右下遍历：用一个变量 pre = 1 记录当前所有经过元素的乘积。
- res[i][j] = pre
- pre = (pre * grid[i][j]) % 12345
从右下到左上遍历：用一个变量 suf = 1 记录当前所有经过元素的乘积。
- res[i][j] = (res[i][j] * suf) % 12345
- suf = (suf * grid[i][j]) % 12345
返回 res。

时间复杂度：$O(n \times m)$。我们只遍历了两次矩阵。
空间复杂度：$O(1)$。除了存储答案的矩阵外，只用了几个变量（pre, suf）。

具体代码

impl Solution {
    pub fn construct_product_matrix(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let m = grid[0].len();
        let n = grid.len();
        let MOD = 12345;

        let mut prefix = vec![1; m * n];
        let mut suffix = 1;

        for k in 1..m*n {
            let i = (k - 1) / m;
            let j = (k - 1) % m;
            prefix[k] = (prefix[k - 1] * (grid[i][j] % MOD) % MOD);
        }

        for k in (0..m*n).rev() {
            let i = k / m;
            let j = k % m;
            prefix[k] = (prefix[k] * suffix) % MOD;
            suffix = (suffix * (grid[i][j] % MOD) % MOD);
        }

        let mut p = grid;
        for i in 0..n {
            for j in 0..m {
                p[i][j] = prefix[i * m + j];
            }
        }
        p
    }
}

beautifulremi / 2906. 构造乘积矩阵

题目