P3890 [GDOI2014] Bit Matrix

Do you know matrix multiplication? For two $n \times n$ matrices $A$ and $B$, suppose $a_{i, j}$ denotes the element in row $i$ and column $j$ of matrix $A$; similarly define $b_{i, j}$ for $B$. If $C = A \times B$, then $c_{i, j} = \sum_{k=1}^{n} a_{i k} \times b_{k j}$. Here $\sum$ is the summation symbol; for example, $\sum_{i=1}^{n} i$ means $1 + 2 + \cdots + n$.

Due to the popularity of The Hobbit, L’s roommate X has recently become interested in the currency they use. For this study, X needs to understand something called a bit matrix. Although a bit matrix is still a matrix, its multiplication is a little different from ordinary matrix multiplication. For bit matrices, $C = A \times B$ means $c_{i, j} = V_{k=1}^{n} a_{i k} \bigoplus b_{k j}$. Here $V$ denotes taking bitwise OR over a sequence; for example, $V_{i=1}^{n} i$ means $1 \mid 2 \mid \cdots \mid n$. The symbol $\mid$ means bitwise OR. Bitwise OR views two numbers in binary: if at bit $i$ at least one of the two numbers is $1$, then the $i$-th bit of the result is $1$; otherwise that bit is $0$. The symbol $\bigoplus$ denotes bitwise XOR: if the $i$-th bits of two binary numbers are different, then the $i$-th bit of the result is $1$; otherwise it is $0$. Here is an example of bit-matrix multiplication. $$\begin{bmatrix}1&6\\3&5\end{bmatrix}\times\begin{bmatrix}3&6\\5&7\end{bmatrix}=\begin{bmatrix}3&7\\0&7\end{bmatrix}$$ Now X would like you to compute $A^{m}$, where $A$ is an $n \times n$ bit matrix, and $A^{m}$ is the result of multiplying $m$ copies of $A$. Precisely: - $A^{1} = A$. - $A^{m} = A^{m-1} \times A$, for $m > 1$.

The first line contains two positive integers $n, m$. The next $n$ lines each contain $n$ non-negative integers; in these $n$ lines, the $j$-th number of the $i$-th line is the element $a_{i, j}$ of the bit matrix.

Output the bit matrix $A^{m}$. That is, print a bit matrix in the same format as the input matrix $A$. See the sample output for details.

Constraints - For $10\%$ of the testdata, $n \le 4$, $m \le 10000$. - For $30\%$ of the testdata, $n \le 10$, $m \le 10^9$. - For $100\%$ of the testdata, $n \le 500$, $m \le 10^9$, and all input integers do not exceed $10^9$. Translated by ChatGPT 5