D - Matrix Pow Sum 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 900 点

問題文

素数 p と N\times N 行列 A = (A_{i,j}) (1\leq i,j\leq N) が与えられます．A の成分は 0 以上 p-1 以下の整数です．

A の成分のうち，0 を全て 1 以上 p-1 以下の整数に置き換えて得られる行列 B は，A に含まれる 0 の個数を K とすると (p-1)^K 個あります．

考えられる B 全てに対する B^p の総和の各成分を p で割った余りを求めてください．

制約

  • 1\leq N\leq 100
  • p は 1\leq p\leq 10^9 を満たす素数
  • 0\leq A_{i,j}\leq p-1
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられます．

N p
A_{1,1} \cdots A_{1,N}
\vdots
A_{N,1} \cdots A_{N,N}

出力

N 行出力してください．

i 行目には j=1,\ldots,N の順に，考えられる B 全てに対する B^p の総和の (i,j) 成分を p で割った余りを空白区切りで出力してください．

入力例 1

2 3
0 1
0 2

出力例 1

0 2
1 2

考えられる B 全てに対する B^p は次の通りです．

  • \begin{pmatrix}1&1 \\ 1&2\end{pmatrix}^3=\begin{pmatrix}5&8 \\ 8&13\end{pmatrix}
  • \begin{pmatrix}1&1 \\ 2&2\end{pmatrix}^3=\begin{pmatrix}9&9 \\ 18&18\end{pmatrix}
  • \begin{pmatrix}2&1 \\ 1&2\end{pmatrix}^3=\begin{pmatrix}14&13 \\ 13&14\end{pmatrix}
  • \begin{pmatrix}2&1 \\ 2&2\end{pmatrix}^3=\begin{pmatrix}20&14 \\ 28&20\end{pmatrix}

これらの総和 \begin{pmatrix}48&44 \\ 67&65\end{pmatrix} の各成分を p=3 で割った余りを出力します．

入力例 2

3 2
1 0 0
0 1 0
0 0 1

出力例 2

1 1 1
1 1 1
1 1 1

考えられる B 全てに対する B^p は次の通りです．

  • \begin{pmatrix}1&1&1 \\ 1&1&1 \\ 1&1&1\end{pmatrix}^2=\begin{pmatrix}3&3&3\\3&3&3\\3&3&3\end{pmatrix}

これらの総和 \begin{pmatrix}3&3&3\\3&3&3\\3&3&3\end{pmatrix} の各成分を p=2 で割った余りを出力します．

入力例 3

4 13
0 1 2 0
3 4 0 5
0 6 0 7
8 9 0 0

出力例 3

8 0 6 5
11 1 8 5
8 0 4 12
8 0 1 9

Score : 900 points

Problem Statement

You are given a prime number p and an N \times N matrix A = (A_{i,j}) (1\leq i,j\leq N). Each element of A is an integer between 0 and p-1, inclusive.

Consider a matrix B obtained by replacing each zero in A with an integer between 1 and p-1, inclusive. There are (p-1)^K such matrices B, where K is the number of zeros in A.

Find each element, modulo p, of the sum of B^p over all possible B.

Constraints

  • 1 \leq N \leq 100
  • p is a prime such that 1 \leq p \leq 10^9.
  • 0 \leq A_{i,j} \leq p-1
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N p
A_{1,1} \cdots A_{1,N}
\vdots
A_{N,1} \cdots A_{N,N}

Output

Print N lines.

The i-th line should contain, in the order j=1,\ldots,N, the (i,j) element of the sum, modulo p, of B^p over all possible B, separated by spaces.

Sample Input 1

2 3
0 1
0 2

Sample Output 1

0 2
1 2

B^p for all possible B are as follows:

  • \begin{pmatrix}1&1 \\ 1&2\end{pmatrix}^3=\begin{pmatrix}5&8 \\ 8&13\end{pmatrix}
  • \begin{pmatrix}1&1 \\ 2&2\end{pmatrix}^3=\begin{pmatrix}9&9 \\ 18&18\end{pmatrix}
  • \begin{pmatrix}2&1 \\ 1&2\end{pmatrix}^3=\begin{pmatrix}14&13 \\ 13&14\end{pmatrix}
  • \begin{pmatrix}2&1 \\ 2&2\end{pmatrix}^3=\begin{pmatrix}20&14 \\ 28&20\end{pmatrix}

Print each element, modulo p=3, of their sum \begin{pmatrix}48&44 \\ 67&65\end{pmatrix}.

Sample Input 2

3 2
1 0 0
0 1 0
0 0 1

Sample Output 2

1 1 1
1 1 1
1 1 1

B^p for all possible B are as follows:

  • \begin{pmatrix}1&1&1 \\ 1&1&1 \\ 1&1&1\end{pmatrix}^2=\begin{pmatrix}3&3&3\\3&3&3\\3&3&3\end{pmatrix}

Print each element, modulo p=2, of their sum \begin{pmatrix}3&3&3\\3&3&3\\3&3&3\end{pmatrix}.

Sample Input 3

4 13
0 1 2 0
3 4 0 5
0 6 0 7
8 9 0 0

Sample Output 3

8 0 6 5
11 1 8 5
8 0 4 12
8 0 1 9