目标
给你一个下标从 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
思路
已知 n x m 矩阵 grid，构造一个乘积矩阵 p 满足 p[i][j] 的值等于除了 grid[i][j] 外所有元素的乘积对 12345 取余。
计算所有元素的乘积会溢出，而保存取模后的乘积不支持除法。
---------
----X----
---------实际上就是要快速计算出 - 的乘积。可以使用前后缀分解计算取模后的乘积。针对每一行进行前后缀分解，前缀的的最后一列以及后缀的第一列就是整行的乘积结果，对这 n 行整行的乘积再次进行前后缀分解。这样就可以快速求出 0 ~ i - 1 行的乘积，以及 i + 1 ~ n - 1 的乘积，然后对第 i 行，使用行的前后缀分解可以快速计算 grid[i][0 ~ j - 1] 以及 grid[i][j + 1 ~ m - 1] 的乘积。
代码
/**
* @date 2026-03-24 8:57
*/
public class ConstructProductMatrix2906 {
public int[][] constructProductMatrix(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int mod = 12345;
int[][] prefix = new int[m][n + 1];
int[][] suffix = new int[m][n + 1];
for (int i = 0; i < m; i++) {
prefix[i][0] = 1;
suffix[i][n] = 1;
for (int j = 0; j < n; j++) {
prefix[i][j + 1] = (int) ((long) prefix[i][j] * grid[i][j] % mod);
suffix[i][n - j - 1] = (int) ((long) suffix[i][n - j] * grid[i][n - j - 1] % mod);
}
}
int[] rowPrefix = new int[m + 1];
int[] rowSuffix = new int[m + 1];
rowPrefix[0] = 1;
rowSuffix[m] = 1;
for (int i = 0; i < m; i++) {
rowPrefix[i + 1] = (int) ((long) rowPrefix[i] * prefix[i][n] % mod);
rowSuffix[m - i - 1] = (int) ((long) rowSuffix[m - i] * suffix[m - i - 1][0] % mod);
}
int[][] p = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
p[i][j] = (int) (((long) rowPrefix[i] * rowSuffix[i + 1] % mod) * ((long) prefix[i][j] * suffix[i][j + 1] % mod) % mod);
}
}
return p;
}
}
性能
