← 返回题目列表

AtCoder · arc190_d

D. 矩阵 Pow Sum

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

给你一个质数 p 和 N \times N 矩阵 A = (A_{i,j}) (1\leq i,j\leq N)。的每个元素 A 是介于 0 和 p-1,包括在内。

考虑一个矩阵 B 通过替换每个零获得 A 之间的整数 1 和 p-1,包括在内。有 (p-1)^K 这样的矩阵 B,其中 K 是 0 的数量 A.

查找每个元素,取模 p,总和 B^p 总体而言 B.

约束

  • 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, (i,j) 和的元素,模 p,属于 B^p 总体而言 B,用空格分隔。


示例输入 1

2 3
0 1
0 2

示例输出 1

0 2
1 2

B^p 对于所有可能 B 如下:

  • \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}

打印每个元素,取模 p=3,其总和 \begin{pmatrix}48&44 \\ 67&65\end{pmatrix}.


示例输入 2

3 2
1 0 0
0 1 0
0 0 1

示例输出 2

1 1 1
1 1 1
1 1 1

B^p 对于所有可能 B 如下:

  • \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}

打印每个元素,取模 p=2,其总和 \begin{pmatrix}3&3&3\\3&3&3\\3&3&3\end{pmatrix}.


示例输入 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