“人工智能”

题号：NC200120
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

外界称为人工智能，行业内还是单独称机器学习，或者潜在特指的深度学习技术，已经逐渐改变了我们的生活，也改变了创新创业团队的idea。众所周知，在每年大家提交的PPT和项目计划书中，都或多或少的使用AI技术创造了巨大的价值和财富，尽管AI省赛的举办都无人知晓，Kaggle和天池等竞赛也几乎无人问津，但还是反映了在学校教学改革和学术鼓励政策的引导下，大家优秀的学术科技创新能力。

深度学习在计算机视觉（Computer Vision）方向里也有使用，目前CV方向各子任务的SOTA（State Of The Art）模型大多都使用了图像卷积及其衍生技术。那么什么是图像卷积呢？

篇幅所限，我们省略诸多数学定义，在这里直接给出一个简要介绍和计算公式：

我们都知道，图像由像素组成，图像可以使用矩阵表示，让每一个矩阵的元素为一个数值，这个数值表示对应坐标的像素值，对于图像的操作都可以转变为矩阵运算。

图像卷积其实是两个矩阵之间的运算，一个是图像的矩阵，一个是卷积核（kernel），我们假设矩阵是 $n$ 阶方阵，卷积核是 $k$ 阶方阵，图像卷积运算结果也是一个方阵，所谓的图像卷积，就是这个公式：

$\sum ^{k}_{i=0}\sum ^{k}_{j=0}g\left( i,j\right) \otimes h\left( k-i,k-j\right)$

或许用GIF表示更为直观：

图中演示的就是

的图像，与

1 0 1
0 1 0
1 0 1

的卷积核进行运算，新矩阵的每一个元素是如图对应区域每一对元素相乘累加的结果。

例如图中如果当前区域图像的元素是：

1 1 1
0 1 1
0 0 1

假设当前区域表示的子矩阵是 $h$ ，卷积核矩阵是 $g$ ，那么这一次卷积的运算结果为：

$\sum ^{k}_{i=0}\sum ^{k}_{j=0}g\left( i,j\right) \ast h\left( i,j\right)$

所以这个位置的值为4，这就是图中左上角的元素。没看懂的话不妨多看几遍GIF，再拿笔演算一下！

对于图像卷积运算，实际上有三种模式：VALID、FULL、SAME，对于每个元素的计算方式都如上所述，但是计算的边界有区别，下面给出边界的状态，橙色是图片image，蓝色是卷积核，灰色是重合区域，白色部分元素的值视为 $0$ 。

VALID模式：当卷积核全部在image里面的时候，进行卷积运算

FULL模式：从卷积核和image刚相交开始做卷积

SAME模式：当卷积核的中心(K)与image的边角重合时，开始做卷积运算。

现在给出图像image和卷积核，请依次输出他们进行VALID、FULL、SAME模式卷积运算的结果。

输入描述:

输入第一行为两个整数 $n$ ， $k$ 表示图像image阶数和卷积核阶数，他们都是方阵。

接下来 $n$ 行，每行 $n$ 个用空格隔开的整数，表示image的数据 $h_{i,j}$

接下来 $k$ 行，每行 $k$ 个用空格隔开的整数，表示卷积核的数据 $g_{i,j}$

$5 \leq n \leq 100$

$k \in \left[ 3,5,7 \right]$

$-5 \leq g_{i,j},h_{i,j} \leq 5$

输出描述:

输出三个矩阵，依次为VALID、FULL、SAME模式的图像卷积运算结果。
每个矩阵设阶数为，那么输出行，每行是空格分隔的整数，表示元素值。

示例1

输入

复制

输出

复制

4 3 4 
2 4 3 
2 3 5 
1 1 2 1 1 0 0 
0 2 2 3 1 1 0 
1 1 4 3 4 1 1 
0 1 2 4 3 3 0 
0 1 2 3 5 1 2 
0 0 2 2 1 2 0 
0 1 1 1 2 0 1 
2 2 3 1 1 
1 4 3 4 1 
1 2 4 3 3 
1 2 3 5 1 
0 2 2 1 2

备注:

按题目中给定计算方式来计算即可，与实际应用的卷积运算的确略有区别，但这里不考虑。