# 2906. 构造乘积矩阵 (Medium)

## 问题描述

[2906. 构造乘积矩阵][link] (Medium)

[link]: 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 <= 10⁵`
- `1 <= m == grid[i].length <= 10⁵`
- `2 <= n * m <= 10⁵`
- `1 <= grid[i][j] <= 10⁹`

## 解题思路

前后缀分解，将矩阵从二维转换为一维，即 $idx = i * n + j$，然后求出前缀乘积数组与后缀乘积数组，注意求取前后缀的时候要取模。

## 代码
```cpp
class Solution {
public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        const int mod = 12345;
        vector<int> prefix(m * n + 1, 1);
        vector<int> suffix(m * n + 1, 1);
        for (int i = 1; i <= m * n; ++i) {
            prefix[i] = ((prefix[i - 1] % mod) * (grid[(i - 1) / n][(i - 1) % n] % mod)) % mod;
            int j = m * n + 1 - i;
            suffix[i] = ((suffix[i - 1] % mod) * (grid[(j - 1) / n][(j - 1) % n] % mod)) % mod;
        }
        vector<vector<int>> p(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int idx = i * n + j;
                p[i][j] = (prefix[idx] % mod * (suffix[m * n - idx - 1] % mod)) % mod;
            }
        }
        return p;
    }
};
```