时间轴

2026-03-24

init

题目：

P2906 构造乘积矩阵

https://leetcode.cn/problems/construct-product-matrix/description/?envType=daily-question&envId=2026-03-24

前缀和换皮题目，注意相乘时可能超过int表示的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <vector>
using std::vector;

#define MODULO_NUM 12345

class Solution {
    public:
        vector<vector<int> > constructProductMatrix(vector<vector<int> > &grid)
        {
                // 1 <= n == grid.length <= 105
                // 1 <= m == grid[i].length <= 105
                // 2 <= n * m <= 105
                // 1 <= grid[i][j] <= 109
                int i, j, m = grid.size(), n = grid[0].size();
                int total = m * n, last;
                vector<vector<int> > product_matrix(m, (vector<int>(n, 0)));
                vector<int> prefix_product(total, 1);
                vector<int> suffix_product(total, 1);

                // prefix
                last = grid[0][0];
                for (i = 0; i < m; i++) {
                        for (j = 0; j < n; j++) {
                                if (i == 0 && j == 0)
                                        continue;

                                prefix_product[i * n + j] =
                                        (long)((long)last * (long)prefix_product[i * n + j - 1]) %
                                        MODULO_NUM;
                                last = grid[i][j];
                        }
                }
                // suffix
                last = grid[m - 1][n - 1];
                for (i = m - 1; i >= 0; i--) {
                        for (j = n - 1; j >= 0; j--) {
                                if (i == m - 1 && j == n - 1)
                                        continue;
                                suffix_product[i * n + j] =
                                        (long)((long)last * (long)suffix_product[i * n + j + 1]) %
                                        MODULO_NUM;
                                last = grid[i][j];
                        }
                }

                for (i = 0; i < m; i++) {
                        for (j = 0; j < n; j++) {
                                product_matrix[i][j] = (long)((long)prefix_product[i * n + j] *
                                                              (long)suffix_product[i * n + j]) %
                                                       MODULO_NUM;
                        }
                }

                return product_matrix;
        }
};