×

计蒜客

  1. 题库
  2. Morgana Net
  3. 问答
  • 19.04%
  • 1000ms
  • 262144K

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 $t$ 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 At that are equal to $1$.

样例输入

2
3 3 1
1 0 1
0 1 0
1 1 1
0 0 0
0 1 0
0 0 0
3 1 100
333 33 3
3 33 333
22 33 2233
22

样例输出

6
0

题目来源

ACM-ICPC 2018 徐州赛区网络预赛

想挑战这道题吗

  • main.c