LeetCode 2906. 构造乘积矩阵

题目链接: https://leetcode.cn/problems/construct-product-matrix/
日期: 2026-03-23
难度: Medium
标签: 前缀和、模运算、取模技巧

一、题目描述

给定一个 n × m 的二维矩阵 grid，定义 p[i][j] 为：矩阵中除 grid[i][j] 外所有元素的乘积，对 12345 取模。

要求返回乘积矩阵 p。

提示：

  • 2 ≤ n × m ≤ 10^5
  • 1 ≤ grid[i][j] ≤ 10^9
  • 不能使用除法

二、踩坑回顾

第一次尝试：除法不可行

看到这道题的第一反应是：先算出所有元素的乘积，然后逐个除以当前元素。

long long total = 1;
for (int r = 0; r < n; r++)
    for (int c = 0; c < m; c++)
        total *= grid[r][c];

p[r][c] = (total / grid[r][c]) % MOD;

问题一：total 会溢出。10^9 的 10^5 次方，这个数字连 long long 都装不下。

问题二：就算我先取模再除，也不行。假设 total = 12345 * 2，取模后 total % 12345 = 0，此时 0 / 2 = 0，而正确答案应该是 2。

关键洞察：除法和取模不能共存

这是本题的核心矛盾。让我把思路理清楚：

total = 12345 * 2

正确算法：
(total / 2) % 12345 = 12345 % 12345 = 0  ← 不对！

如果先取模：
(total % 12345) / 2 = 0 / 2 = 0  ← 信息丢失！

原因：取模是一种”单向压缩”。压缩后的数字已经丢失了”哪些因子构成了它”的信息，除法无法逆推回去。

而且本题的 MOD = 12345 = 3 × 5 × 823，不是质数。即使想用乘法逆元来绕过除法，当 grid[i][j] 包含因子 3 或 5 时，逆元根本不存在。

提示的启发：前后缀分解

提示说要用前后缀乘积。乍一看有点懵——前后缀不是一维数组的做法吗？二维矩阵怎么办？

后来想通了：把二维矩阵按行摊平成一维数组，前后缀的思路就自然成立了。

核心思想：

  • pre[i] = 下标 i 左边所有元素的乘积
  • suf[i] = 下标 i 右边所有元素的乘积
  • 答案 p[i] = pre[i] × suf[i]

这样就完全绕开了除法。

三、解题思路

前后缀乘积的正确打开方式

设摊平后的一维数组为 nums，长度为 L = n × m。

位置 i:  [a, b, c, d, ...]
            ↑     ↑
          pre[i] suf[i]
  • pre[i]：下标 0 到 i-1 的乘积（不含 i）
  • suf[i]：下标 i+1 到 L-1 的乘积（不含 i）

所以 p[i] = pre[i] × suf[i] % MOD。

构造方法

// pre[i] 表示 nums[0...i-1] 的积
vector<long long> pre(L + 1, 1);
for (int i = 0; i < L; i++)
    pre[i + 1] = (pre[i] * nums[i]) % MOD;

// suf[i] 表示 nums[i...L-1] 的积
vector<long long> suf(L + 1, 1);
for (int i = L - 1; i >= 0; i--)
    suf[i] = (suf[i + 1] * nums[i]) % MOD;

// 位置 i 的答案：左边 × 右边
res[i] = (pre[i] * suf[i + 1]) % MOD;

更进一步的优化：原地两遍扫描

上面用到了三个辅助数组（nums、pre、suf），其实可以更省。

直接利用返回矩阵 p 作为”前缀”的存储介质，两遍扫描搞定：

// 第一遍：计算前缀积，存入 p
long long curr = 1;
for (int r = 0; r < n; r++) {
    for (int c = 0; c < m; c++) {
        p[r][c] = curr;  // 此时存的是"左边所有人的积"
        curr = (curr * grid[r][c]) % MOD;
    }
}

// 第二遍：计算后缀积，与前缀相乘
curr = 1;
for (int r = n - 1; r >= 0; r--) {
    for (int c = m - 1; c >= 0; c--) {
        p[r][c] = (p[r][c] * curr) % MOD;  // 前缀 × 后缀
        curr = (curr * grid[r][c]) % MOD;
    }
}

第一遍结束后，p[r][c] 存的是 (r,c) 左上方所有元素的积。

第二遍逆序遍历时，p[r][c] 再乘上 (r,c) 右下方所有元素的积。

由于”当前元素”始终没有被乘进去，完美绕过了”除以自己”的问题。

四、代码实现

class Solution {
public:
    const int MOD = 12345;

    vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> p(n, vector<int>(m));
        
        long long curr = 1;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                p[r][c] = curr;
                curr = (curr * (grid[r][c] % MOD)) % MOD;
            }
        }
        
        curr = 1;
        for (int r = n - 1; r >= 0; r--) {
            for (int c = m - 1; c >= 0; c--) {
                p[r][c] = (1LL * p[r][c] * curr) % MOD;
                curr = (curr * (grid[r][c] % MOD)) % MOD;
            }
        }
        
        return p;
    }
};

五、复杂度分析

维度 分析
时间 O(n × m) - 两遍扫描
空间 O(1) - 除了返回矩阵外，只用几个 long long 变量

六、心得总结

为什么这道题值得写成博客？

这道题表面是”矩阵操作”，本质上是模运算的取舍问题。它让我彻底理解了一件事：

取模是一种单向压缩。加法/乘法可以放心取模，除法/逆元不能。

什么时候必须用前后缀分解？

场景 单遍扫描可行？ 原因
求所有元素和 ✅ 减法是加法的逆元
求所有元素积 ❌ 除以自己 ≠ 减去自己
“除自身外的全局统计量” ❌ 必须绕过除法

前后缀分解的核心思想

把”缺失的元素”想成一个空洞。与其费力去”减去”或”除以”，不如分别在空洞的左边和右边构造积，最后拼起来。

这个思想可以推广到：

  • 接雨水（左右最高墙）
  • 斐波那契前缀和
  • 二维前缀和/积

[!NOTE]

当你发现”减去自己”或”除以自己”做不到时，就该想到”左 + 右”的前后缀分解。

七、相关题目