题目描述
给你一个下标从 0 开始、大小为 n * m
的二维整数矩阵 grid
,定义一个下标从 0 开始、大小为 n * m
的的二维矩阵 p
。如果满足以下条件,则称 p
为 grid
的 乘积矩阵:
- 对于每个元素
p[i][j]
,它的值等于除了grid[i][j]
外所有元素的乘积。乘积对12345
取余数。
返回 grid
的乘积矩阵。
样例
输入: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]]。
输入: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
算法
(前后缀分解) $O(mn)$
- 由于
12345
不是质数,且有可能不与grid
互质,所以无法通过乘法逆元的操作直接从全部数字的乘积上去除每个位置的数字。 - 考虑前后缀分解。
- 先预处理每一行的完整乘积,求出后面所有行的后缀乘积。
- 然后枚举每一行,同时维护前面所有行的前缀乘积。对于每一行,采取同样的前后缀分解,先求出这一行的所有后缀乘积,然后枚举每一个位置,同时维护这一行的前缀乘积,最后四个前后缀乘到一起就是当前位置的答案。
时间复杂度
- 需要 $O(mn)$ 的时间预处理行的后缀,同时对于每一行,需要 $O(n)$ 的时间处理当前行的每一列的后缀和答案。
- 故总时间复杂度为 $O(mn)$。
空间复杂度
- 需要 $O(m + n)$ 的额外空间存储行和列的前后缀。
C++ 代码
class Solution {
public:
vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
const int mod = 12345;
const int m = grid.size(), n = grid[0].size();
vector<int> suf_row(m + 1);
suf_row[m] = 1;
for (int i = m - 1; i >= 0; i--) {
int r = 1;
for (int j = 0; j < n; j++) {
grid[i][j] %= mod;
r = r * grid[i][j] % mod;
}
suf_row[i] = suf_row[i + 1] * r % mod;
}
vector<vector<int>> ans(m, vector<int>(n));
int pre_row = 1;
for (int i = 0; i < m; i++) {
vector<int> suf_col(n + 1);
suf_col[n] = 1;
for (int j = n - 1; j >= 0; j--)
suf_col[j] = suf_col[j + 1] * grid[i][j] % mod;
int pre_col = 1;
for (int j = 0; j < n; j++) {
ans[i][j] = pre_row * suf_row[i + 1] % mod *
pre_col % mod * suf_col[j + 1] % mod;
pre_col = pre_col * grid[i][j] % mod;
}
pre_row = pre_row * pre_col % mod;
}
return ans;
}
};