Convolution Layer

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 256000/256000 K (Java/Others)

Description

In Convolutional Neural Networks(CNNs), the convolution layer is the most import component.

The convolution layer have two 4-dimension arrays: $I \in \mathbb{R}^{num_{in} \times channel_{in} \times h_{in} \times w_{in}}$ and $W \in \mathbb{R}^{num_{w} \times channel_{w} \times h_{w} \times w_{w}}$, and get a 4-dimension array: $O \in \mathbb{R}^{num_{out} \times channel_{out} \times h_{out} \times w_{out}}$, where $num_{out} = num_{in}, channel_{out} = num_{w}, h_{out} = (h_{in} - h_w) / stride_h + 1, w_{out} = (w_{in} - w_w) / stride_w + 1$, and $channel_{in}$ must be equal to $channel_{w}$. $stride_w$, $stride_h$ is the parameters of CNNs.(We ignore other parameters like pad.)

We can use the following formula to represent a simple convolution layer:
$$O[n][m][x][y] = \sum_{c = 0}^{channel_{in} - 1}{\sum_{i=0}^{h_w - 1}{\sum_{j=0}^{w_w - 1}{I[n][c][x \times stride_{h} + i][ y \times stride_w + j] \cdot W[m][c][i][j]}}}$$$$\begin{array}{lll}
n &=& 0,\cdots, num_{out} - 1\\
m &=& 0, \cdots, channel_{out} - 1 \\
x &=& 0, \cdots, h_{out} - 1 \\
y &=& 0, \cdots, w_{out} - 1
\end{array}$$

Today, Xiaoming find a special convolution layer, The value of each element in $I$ and $W$ is either -1 or +1. Please help he compute $O$.

Input

In the first line there are four integers: $num_{in}$, $channel_{in}$, $h_{in}$, $w_{in}$;
In the second line there are $num_{in} \times channel_{in} \times h_{in} \times w_{in}$ integers, represent $I$. The value of each element in $I$ is -1 or +1.
In the third line there are four integers: $num_w, channel_w, h_w, w_w$.
In the fourth line there are $num_{w} \times channel_{w} \times h_{w} \times w_{w}$ integers, represent $W$. The value of each element in $W$ is -1 or +1;
In the fifth line there are two integers: $stride_h$, $stride_w$.

Except for the sample,
$num_{in} = 10, channel_{in} = 64, h_{in} = 56, w_{in} = 56$
$num_{w} = 64, channel_w = channel_{in}, h_w = 11, w_w = 11$
$stride_{h} = 1, stride_{w} = 1$

Output

First, print four integers: $num_{out}$, $channel_{out}$, $h_{out}$, $w_{out}$ in a line.
Then print an integer $ans \bmod {2^{32}}$ in a line, so that
$$ans = \sum_{n=0}^{num_{out-1}}{\sum_{m=0}^{channel_{out} - 1}{\sum_{x=0}^{h_{out} - 1}{\sum_{y=0}^{w_{out} - 1}{O[n][m][x][y] * (((n * channel_{out} + m) * h_{out} + x) * w_{out} + y)}}}}$$

Sample Input

1 1 5 5 -1 1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 3 3 1 -1 1 -1 1 -1 1 1 -1 1 1

Sample Output

1 1 3 3 4294967286

Hint

liuyiding

Source

2017中国大学生程序设计竞赛 - 网络选拔赛

提交代码