2906.构造乘积矩阵：前后缀分解

【LetMeFly】2906.构造乘积矩阵：前后缀分解

力扣题目链接：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 <= 105
• 1 <= m == grid[i].length <= 105
• 2 <= n * m <= 105
• 1 <= grid[i][j] <= 109

一维版本：238. 除了自身以外数组的乘积

解题方法一：前后缀分解 O(mn)空间

由于模数并非质数，所以不方便全部求积后通过模逆元做除法，因此可以使用前缀和和后缀和两个数组，分别记录每个位置前面元素的乘积以及后面元素的乘积。

二维数组怎么定义“前面的元素”和“后面的元素”呢？很简单，把$n$行$m$列的二维数组看成$n\times m$大小的一维数组就好了，一维数组的下标$t$在原始二维数组中的下标是$(\lfloor\frac{t}{m}\rfloor, t\ %\ m)$。

• 时间复杂度$O(nm)$
• 空间复杂度$O(nm)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-24 22:02:21
 */
typedef long long ll;
const ll MOD = 12345;
class Solution {
public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        auto getIndex = [&](const int& t) {
            return pair<int, int>{t / m, t % m};
        };

        vector<vector<ll>> prefix(n, vector<ll>(m, 1));
        for (int t = 1; t < m * n; t++) {
            auto [i1, j1] = getIndex(t);
            auto [i0, j0] = getIndex(t - 1);
            prefix[i1][j1] = prefix[i0][j0] * grid[i0][j0] % MOD;
        }

        vector<vector<ll>> suffix(n, vector<ll>(m, 1));
        for (int t = m * n - 2; t >= 0; t--) {
            auto [i0, j0] = getIndex(t);
            auto [i1, j1] = getIndex(t + 1);
            suffix[i0][j0] = suffix[i1][j1] * grid[i1][j1] % MOD;
        }

        vector<vector<int>> ans(n, vector<int>(m, 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[i][j] = prefix[i][j] * suffix[i][j] % MOD;
            }
        }
        return ans;
    }
};

解题方法二：前后缀分解 O(1)空间

函数返回值是不计入算法空间复杂度的，所以在计算前缀数组时，我们可以直接把前缀数组保存在答案数组中；在计算后缀数组的过程中，顺便把答案也算出来就好了。

• 时间复杂度$O(nm)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-24 22:07:50
 */
typedef long long ll;
const ll MOD = 12345;
class Solution {
public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        auto getIndex = [&](const int& t) {
            return pair<int, int>{t / m, t % m};
        };

        vector<vector<int>> ans(n, vector<int>(m, 1));
        for (int t = 1; t < m * n; t++) {
            auto [i1, j1] = getIndex(t);
            auto [i0, j0] = getIndex(t - 1);
            ans[i1][j1] = (ll)ans[i0][j0] * grid[i0][j0] % MOD;
        }

        ll suffix = 1;
        for (int t = m * n - 2; t >= 0; t--) {
            auto [i0, j0] = getIndex(t);
            auto [i1, j1] = getIndex(t + 1);
            suffix = suffix * grid[i1][j1] % MOD;
            ans[i0][j0] = ans[i0][j0] * suffix % MOD;
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源