# 描述

Morgana is learning Convolutional Neural Network, he builds a neural network called “morgana net”.

In brief, given a $N \times N$ matrix $A$ that represents a picture. Every layer in morgana net is doing work as follow:

$$\displaystyle A_{k+1}[i][j] = f(\sum_{p = i - m}^{i + m}\sum_{q = j - m}^{j + m} A_k[p][q]\ B[p - i + m + 1][q - j + m + 1])$$

Every layer can be represented by a $N \times N$ matrix $A_k$​ and $A_k$​ means it is the $k$th layer. $B$ is the $(2m+1) \times (2m+1)$ matrix represents convolution kernel. And if $(p, q)$ are out of $A$, $A[p][q]$ will be $0$ (if $p \le 0$ or $q \le 0$ or $p > n$ or $q > n$). $f(x)$ is the activation function and in morgana net $f(x) = x \mod 2$.

Now morgana gives you the input $A_0$​ represents a picture, he wants to know after ttt layers, how many nerve cells’ value are equal to $1$ . (that means how many elements in At are equal to $1$).

## Input

First line contains one integer $T (T \le 100)$.

Then the first line of each case contains three integers $N$ and $M$, $t$ ( $M$ equals to $2m+1$ ). ($1 \le N \le 8$ , $1 \le M \le N$, $1 \le t \le 1e9$).

The next $N$ lines describes the $N \times N$ matrix $A$ ($0 \le A_{i,j} \le 1e9$).

Then the next $M$ lines describes the $M \times M$ matrix $B$ ($0 \le B_{i,j} \le 1e9$).

## Output

For each case, output the number of elements in $A_t$ that are equal to $1$.

# 思路

• 知道卷积的意义后就可以构造出一个转移矩阵，来加速多次卷积的运算。
• 这里我们需要把$A$矩阵降维，才能根据上面的式子构造出转移矩阵$tr$
• 例如样例1：
$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} a_{0,0} \\ a_{0,1} \\ a_{0,2} \\ a_{1,0} \\ a_{1,1} \\ a_{1,2} \\ a_{2,0} \\ a_{2,1} \\ a_{2,2} \end{pmatrix}$$
（没错，转移矩阵就是个单位阵）
• 因为只要关心结果的奇偶，所以矩阵快速幂可以压位进行。但是良心的出题人并没有卡这个。
• 看代码应该能理解其中的道理。(代码中的矩阵进行了转置)

0%