**方法一：前后缀分解**

我们可以预处理出每个元素的后缀乘积（不包含自身），然后再遍历矩阵，计算得到每个元素的前缀乘积（不包含自身），将两者相乘即可得到每个位置的结果。

具体地，我们用 $p[i][j]$ 表示矩阵中第 $i$ 行第 $j$ 列元素的结果，定义一个变量 $suf$ 表示当前位置右下方的所有元素的乘积，初始时 $suf = 1$。我们从矩阵右下角开始遍历，对于每个位置 $(i, j)$，我们将 $suf$ 赋值给 $p[i][j]$，然后更新 $suf$ 为 $suf \times grid[i][j] \bmod 12345$，这样就可以得到每个位置的后缀乘积。

接下来我们从矩阵左上角开始遍历，对于每个位置 $(i, j)$，我们将 $p[i][j]$ 乘上 $pre$，再对 $12345$ 取模，然后更新 $pre$ 为 $pre \times grid[i][j] \bmod 12345$，这样就可以得到每个位置的前缀乘积。

遍历结束，返回结果矩阵 $p$ 即可。

时间复杂度 $O(n \times m)$，其中 $n$ 和 $m$ 分别是矩阵的行数和列数。忽略结果矩阵的空间占用，空间复杂度 $O(1)$。

class Solution:

def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:

n, m = len(grid), len(grid[0])

p = [[0] * m for _ in range(n)]

mod = 12345

suf = 1

for i in range(n - 1, -1, -1):

for j in range(m - 1, -1, -1):

p[i][j] = suf

suf = suf * grid[i][j] % mod

pre = 1

for i in range(n):

for j in range(m):

p[i][j] = p[i][j] * pre % mod

pre = pre * grid[i][j] % mod

return p

class Solution {

public int[][] constructProductMatrix(int[][] grid) {

final int mod = 12345;

int n = grid.length, m = grid[0].length;

int[][] p = new int[n][m];

long suf = 1;

for (int i = n - 1; i >= 0; --i) {

for (int j = m - 1; j >= 0; --j) {

p[i][j] = (int) suf;

suf = suf * grid[i][j] % mod;

}

}

long pre = 1;

for (int i = 0; i < n; ++i) {

for (int j = 0; j < m; ++j) {

p[i][j] = (int) (p[i][j] * pre % mod);

pre = pre * grid[i][j] % mod;

}

}

return p;

}

}

class Solution {

public:

vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {

const int mod = 12345;

int n = grid.size(), m = grid[0].size();

vector<vector<int>> p(n, vector<int>(m));

long long suf = 1;

for (int i = n - 1; i >= 0; --i) {

for (int j = m - 1; j >= 0; --j) {

p[i][j] = suf;

suf = suf * grid[i][j] % mod;

}

}

long long pre = 1;

for (int i = 0; i < n; ++i) {

for (int j = 0; j < m; ++j) {

p[i][j] = p[i][j] * pre % mod;

pre = pre * grid[i][j] % mod;

}

}

return p;

}

};

function constructProductMatrix(grid: number[][]): number[][] {

const mod = 12345;

const [n, m] = [grid.length, grid[0].length];

const p: number[][] = Array.from({ length: n }, () => Array.from({ length: m }, () => 0));

let suf = 1;

for (let i = n - 1; ~i; --i) {

for (let j = m - 1; ~j; --j) {

p[i][j] = suf;

suf = (suf * grid[i][j]) % mod;

}

}

let pre = 1;

for (let i = 0; i < n; ++i) {

for (let j = 0; j < m; ++j) {

p[i][j] = (p[i][j] * pre) % mod;

pre = (pre * grid[i][j]) % mod;

}

}

return p;

}

impl Solution {

pub fn construct_product_matrix(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {

let modulo: i32 = 12345;

let n = grid.len();

let m = grid[0].len();

let mut p: Vec<Vec<i32>> = vec![vec![0; m]; n];

let mut suf = 1;

for i in (0..n).rev() {

for j in (0..m).rev() {

p[i][j] = suf;

suf = (suf as i64 * grid[i][j] as i64 % modulo as i64) as i32;

}

}

let mut pre = 1;

for i in 0..n {

for j in 0..m {

p[i][j] = (p[i][j] as i64 * pre as i64 % modulo as i64) as i32;

pre = (pre as i64 * grid[i][j] as i64 % modulo as i64) as i32;

}

}

p

}

}

**Solution 1: Prefix and Suffix Decomposition**

We can preprocess the suffix product (excluding itself) of each element, and then traverse the matrix to calculate the prefix product (excluding itself) of each element. The product of the two gives us the result for each position.

Specifically, we use $p[i][j]$ to represent the result of the element in the $i$-th row and $j$-th column of the matrix. We define a variable $suf$ to represent the product of all elements below and to the right of the current position. Initially, $suf$ is set to $1$. We start traversing from the bottom right corner of the matrix. For each position $(i, j)$, we assign $suf$ to $p[i][j]$, and then update $suf$ to $suf \times grid[i][j] \bmod 12345$. This way, we can obtain the suffix product of each position.

Next, we start traversing from the top left corner of the matrix. For each position $(i, j)$, we multiply $p[i][j]$ by $pre$, take the result modulo $12345$, and then update $pre$ to $pre \times grid[i][j] \bmod 12345$. This way, we can obtain the prefix product of each position.

After the traversal, we return the result matrix $p$.

The time complexity is $O(n \times m)$, where $n$ and $m$ are the number of rows and columns in the matrix, respectively. Ignoring the space occupied by the result matrix, the space complexity is $O(1)$.

class Solution:

def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:

n, m = len(grid), len(grid[0])

p = [[0] * m for _ in range(n)]

mod = 12345

suf = 1

for i in range(n - 1, -1, -1):

for j in range(m - 1, -1, -1):

p[i][j] = suf

suf = suf * grid[i][j] % mod

pre = 1

for i in range(n):

for j in range(m):

p[i][j] = p[i][j] * pre % mod

pre = pre * grid[i][j] % mod

return p

class Solution {

public int[][] constructProductMatrix(int[][] grid) {

final int mod = 12345;

int n = grid.length, m = grid[0].length;

int[][] p = new int[n][m];

long suf = 1;

for (int i = n - 1; i >= 0; --i) {

for (int j = m - 1; j >= 0; --j) {

p[i][j] = (int) suf;

suf = suf * grid[i][j] % mod;

}

}

long pre = 1;

for (int i = 0; i < n; ++i) {

for (int j = 0; j < m; ++j) {

p[i][j] = (int) (p[i][j] * pre % mod);

pre = pre * grid[i][j] % mod;

}

}

return p;

}

}

class Solution {

public:

vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {

const int mod = 12345;

int n = grid.size(), m = grid[0].size();

vector<vector<int>> p(n, vector<int>(m));

long long suf = 1;

for (int i = n - 1; i >= 0; --i) {

for (int j = m - 1; j >= 0; --j) {

p[i][j] = suf;

suf = suf * grid[i][j] % mod;

}

}

long long pre = 1;

for (int i = 0; i < n; ++i) {

for (int j = 0; j < m; ++j) {

p[i][j] = p[i][j] * pre % mod;

pre = pre * grid[i][j] % mod;

}

}

return p;

}

};

function constructProductMatrix(grid: number[][]): number[][] {

const mod = 12345;

const [n, m] = [grid.length, grid[0].length];

const p: number[][] = Array.from({ length: n }, () => Array.from({ length: m }, () => 0));

let suf = 1;

for (let i = n - 1; ~i; --i) {

for (let j = m - 1; ~j; --j) {

p[i][j] = suf;

suf = (suf * grid[i][j]) % mod;

}

}

let pre = 1;

for (let i = 0; i < n; ++i) {

for (let j = 0; j < m; ++j) {

p[i][j] = (p[i][j] * pre) % mod;

pre = (pre * grid[i][j]) % mod;

}

}

return p;

}

impl Solution {

pub fn construct_product_matrix(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {

let modulo: i32 = 12345;

let n = grid.len();

let m = grid[0].len();

let mut p: Vec<Vec<i32>> = vec![vec![0; m]; n];

let mut suf = 1;

for i in (0..n).rev() {

for j in (0..m).rev() {

p[i][j] = suf;

suf = (suf as i64 * grid[i][j] as i64 % modulo as i64) as i32;

}

}

let mut pre = 1;

for i in 0..n {

for j in 0..m {

p[i][j] = (p[i][j] as i64 * pre as i64 % modulo as i64) as i32;

pre = (pre as i64 * grid[i][j] as i64 % modulo as i64) as i32;

}

}

p

}

}

class Solution {

vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {

const int mod = 12345;

int n = grid.size(), m = grid[0].size();

vector<vector<int>> p(n, vector<int>(m));

long long suf = 1;

for (int i = n - 1; i >= 0; --i) {

for (int j = m - 1; j >= 0; --j) {

p[i][j] = suf;

suf = suf * grid[i][j] % mod;

}

}

long long pre = 1;

for (int i = 0; i < n; ++i) {

for (int j = 0; j < m; ++j) {

p[i][j] = p[i][j] * pre % mod;

pre = pre * grid[i][j] % mod;

}

}

return p;

}

};