Morgana Net(矩阵快速幂)

描述

传送门:ACM-ICPC 2018 徐州赛区网络预赛 - Problem K

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$.

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
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

样例输出

1
2
6
0

思路

  • 知道卷积的意义后就可以构造出一个转移矩阵,来加速多次卷积的运算。
  • 这里我们需要把$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}
    $$
    (没错,转移矩阵就是个单位阵)
  • 因为只要关心结果的奇偶,所以矩阵快速幂可以压位进行。但是良心的出题人并没有卡这个。
  • 看代码应该能理解其中的道理。(代码中的矩阵进行了转置)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;

mat mul(const mat& A, const mat& B)
{
mat C(A.size(), vec(B[0].size()));
for (int i = 0; i < A.size(); i++)
for (int k = 0; k < B.size(); k++)
if (A[i][k])
for (int j = 0; j < B[0].size(); j++)
C[i][j] ^= (A[i][k] & B[k][j]);
return C;
}
mat Pow(mat A, long long n)
{
mat B(A.size(), vec(A.size()));
for (int i = 0; i < A.size(); i++) B[i][i] = 1;
for (; n; n >>= 1, A = mul(A, A))
if (n & 1) B = mul(B, A);
return B;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T;
scanf("%d", &T);
while (T--)
{
int n, m, t;
scanf("%d%d%d", &n, &m, &t);
mat b(m, vec(m));
mat a(1, vec(n * n));
for (int i = 0; i < n * n; i++)
{
scanf("%d", &a[0][i]);
a[0][i] &= 1;
}
for (int i = 0; i < m; i++)
for (int j = 0; j < m; j++)
{
scanf("%d", &b[i][j]);
b[i][j] &= 1;
}
m >>= 1;
mat tr(n * n, vec(n * n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int p = max(i - m, 0); p <= min(i + m, n - 1); p++)
for (int q = max(j - m, 0); q <= min(j + m, n - 1); q++)
tr[p * n + q][i * n + j] = b[p - i + m][q - j + m];
a = mul(a, Pow(tr, t));
printf("%d\n", accumulate(a[0].begin(), a[0].end(), 0));
}
return 0;
}
捐助作者
0%