程式語言 - LeetCode - C++ - 2906. Construct Product Matrix


參考資訊：
https://algo.monster/liteproblems/2906

題目：


方法： 

// 原始公式
(位置0) = grid[0][1] * grid[1][0] * grid[1][1]
(位置1) = grid[0][0] * grid[1][0] * grid[1][1]
(位置2) = grid[0][0] * grid[0][1] * grid[1][1]
(位置3) = grid[0][0] * grid[0][1] * grid[1][0]

// 轉換成一維
(位置0) = grid[1] * grid[2] * grid[3]
(位置1) = grid[0] * grid[2] * grid[3]
(位置2) = grid[0] * grid[1] * grid[3]
(位置3) = grid[0] * grid[1] * grid[2]

// Prefix (由前往後)
(位置0) = 1
(位置1) = grid[0]
(位置2) = grid[0] * grid[1]
(位置3) = grid[0] * grid[1] * grid[2]

// Suffix (由後往前)
(位置0) = grid[1] * grid[2] * grid[3]
(位置1) = grid[2] * grid[3]
(位置2) = grid[3]
(位置3) = 1

// Result = Prefix * Suffix
(位置0) = 1 * grid[1] * grid[2] * grid[3]
(位置1) = grid[0] * grid[2] * grid[3]
(位置2) = grid[0] * grid[1] * grid[3]
(位置3) = grid[0] * grid[1] * grid[2] * 1

解答： 

class Solution {
public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
        using ll = long long;
        const int MOD = 12345;

        int row_size = grid.size();
        int col_size = grid[0].size();
        int total = row_size * col_size;

        vector<ll> q(total);

        for (int i = 0; i < row_size; ++i) {
            for (int j = 0; j < col_size; ++j) {
                q[(i * col_size) + j] = grid[i][j];
            }
        }

        vector<ll> prefix(total, 1);
        vector<ll> suffix(total, 1);
        vector<vector<int>> r(row_size, vector<int>(col_size));

        for (int i = 1; i < total; ++i) {
            prefix[i] = (prefix[i - 1] * q[i - 1]) % MOD;
        }

        for (int i = total - 2; i >= 0; --i) {
            suffix[i] = (suffix[i + 1] * q[i + 1]) % MOD;
        }

        for (int i = 0; i < total; ++i) {
            int v = (prefix[i] * suffix[i]) % MOD;

            r[i / col_size][i % col_size] = v;
        }

        return r;
    }
};