题目内容

需要在模 $MOD$ 的整数域中，完成一个由多层双向循环神经网络和多头自注意力组成的网络的一次前向计算。

输入序列共有 $N$ 个位置，位置 $t$ 的原始输入向量记为 $x_t$，其维度为 $F$。网络先经过 $S$ 层双向 RNN 编码，再进行包含 $A$ 个注意力头的多头自注意力计算，之后通过残差连接，最后使用线性输出层得到 $C$ 维向量 $y_t$。

所有向量均视为行向量，矩阵乘法均采用“行向量乘矩阵”的方式。所有输入参数均为满足 $0\le x<MOD$ 的非负整数。每次完成向量加法、点积或矩阵乘法后，都需要将结果对 $MOD$ 取模。

1. 多层双向 RNN 编码

对于双向 RNN 的第 $l$ 层，位置 $t$ 的输入记为 $a_t^{(l)}$。第一层直接使用原始输入，即 $a_t^{(1)}=x_t$。

每一层的输入维度记作 $d_l$，其中 $d_l=\begin{cases}F,&l=1\\2R,&l>1\end{cases}$。

这里，$R$ 是单个方向的隐藏状态维度。因此，一层双向 RNN 在每个位置都会分别产生一个 $R$ 维正向状态和一个 $R$ 维反向状态。

第 $l$ 层正向计算所使用的参数为 $U_f^{(l)}$、$V_f^{(l)}$、$c_f^{(l)}$，其规模依次为 $d_l\times R$、$R\times R$、$1\times R$。该方向的给定初始状态为 $p_0^{(l)}$，规模为 $1\times R$。

正向状态从位置 $1$ 开始，按照 $1,2,\dots,N$ 的顺序计算。对于每个 $t$，有 $p_t^{(l)}=\left(a_t^{(l)}U_f^{(l)}+p_{t-1}^{(l)}V_f^{(l)}+c_f^{(l)}\right)\bmod MOD$。

同一层的反向计算使用 $U_b^{(l)}$、$V_b^{(l)}$、$c_b^{(l)}$，规模分别为 $d_l\times R$、$R\times R$、$1\times R$。反向方向的给定初始状态为 $r_{N+1}^{(l)}$，其规模为 $1\times R$。

反向状态的计算次序与正向相反，从位置 $N$ 开始依次处理到位置 $1$。对于每个 $t$，有 $r_t^{(l)}=\left(a_t^{(l)}U_b^{(l)}+r_{t+1}^{(l)}V_b^{(l)}+c_b^{(l)}\right)\bmod MOD$。

当第 $l$ 层的两个方向均计算完成后，把同一位置上的正向状态放在前、反向状态放在后进行拼接。若 $l<S$，该结果作为下一层对应位置的输入，即 $a_t^{(l+1)}=\left[p_t^{(l)}\parallel r_t^{(l)}\right]$。

因此，从第 $2$ 层开始，每个 $a_t^{(l)}$ 的维度均为 $2R$。

经过全部 $S$ 层双向 RNN 后，取最后一层在位置 $t$ 的两个方向状态，并定义 $e_t=\left[p_t^{(S)}\parallel r_t^{(S)}\right]$。

此时 $e_t\in\mathbb{Z}_{MOD}^{2R}$，它将作为后续多头自注意力部分的输入。

2. 多头自注意力

多头自注意力共有 $A$ 个注意力头，注意力头编号为 $h=0,1,\dots,A-1$，每个头的维度为 $Q$。

本题使用未归一化的点积注意力，不进行缩放、不使用 softmax，也不存在 mask。

对于任意注意力头 $h$，均给定三个规模为 $2R\times Q$ 的矩阵 $Q_h$、$K_h$、$V_h$。在位置 $t$，分别计算 $q_t^{(h)}=e_tQ_h\bmod MOD$、$k_t^{(h)}=e_tK_h\bmod MOD$、$v_t^{(h)}=e_tV_h\bmod MOD$。

上述三个向量均为 $Q$ 维，即 $q_t^{(h)},k_t^{(h)},v_t^{(h)}\in\mathbb{Z}_{MOD}^{Q}$。

接下来，对于位置 $t$ 和位置 $s$，利用 $q_t^{(h)}$ 与 $k_s^{(h)}$ 的点积计算第 $h$ 个注意力头的注意力分数：

$\beta_{t,s}^{(h)}=\left(\sum_{j=0}^{Q-1}q_t^{(h)}[j]\cdot k_s^{(h)}[j]\right)\bmod MOD$。

得到位置 $t$ 对所有位置的注意力分数后，对每个分量 $j=0,1,\dots,Q-1$ 计算：

$c_t^{(h)}[j]=\left(\sum_{s=1}^{N}\beta_{t,s}^{(h)}\cdot v_s^{(h)}[j]\right)\bmod MOD$。

由此得到第 $h$ 个注意力头在位置 $t$ 的 $Q$ 维输出 $c_t^{(h)}$。

对于同一个位置 $t$，将各注意力头的结果按照编号 $0,1,\dots,A-1$ 的顺序拼接，得到 $c_t=\left[c_t^{(0)}\parallel c_t^{(1)}\parallel\dots\parallel c_t^{(A-1)}\right]$。

拼接后的向量满足 $c_t\in\mathbb{Z}_{MOD}^{AQ}$。

3. 残差连接

多头自注意力产生的 $AQ$ 维向量 $c_t$ 需要通过投影矩阵 $W_p$ 映射到 $2R$ 维。

其中，$W_p$ 的规模为 $AQ\times 2R$，偏置 $c_p$ 的规模为 $1\times 2R$。

投影结果与同一位置的编码结果 $e_t$ 进行残差相加，得到 $u_t=\left(c_tW_p+c_p+e_t\right)\bmod MOD$。

4. 输出层

残差连接后的 $u_t$ 通过最后的线性层得到位置 $t$ 的输出。

输出层包含规模为 $2R\times C$ 的矩阵 $W_y$ 和规模为 $1\times C$ 的偏置 $c_y$，计算方式为 $y_t=\left(u_tW_y+c_y\right)\bmod MOD$。

最终得到 $y_t\in\mathbb{Z}_{MOD}^{C}$。需要计算输入序列全部 $N$ 个位置对应的最终输出向量。

输入描述

第一行给出 $8$ 个整数 $N$、$F$、$R$、$C$、$S$、$A$、$Q$、$MOD$，分别表示序列长度、输入维度、单向隐藏状态维度、输出维度、双向 RNN 层数、注意力头数量、每个注意力头的维度以及模数。

数据范围为：

$1\le N\le 10,\ 1\le F\le 5,\ 1\le R\le 5$。

$1\le C\le 5,\ 1\le S\le 3,\ 1\le A\le 4,\ 1\le Q\le 4$。

$2\le MOD\le 97$。

随后给出原始输入序列，共 $N$ 行。第 $t$ 行包含 $F$ 个整数，表示位置 $t$ 的向量 $x_t$。

原始输入之后是 $S$ 层双向 RNN 的参数，各层按照 $l=1,2,\dots,S$ 的顺序给出。对于当前层 $l$，输入维度为 $d_l=\begin{cases}F,&l=1\\2R,&l>1\end{cases}$。

每一层内部的参数输入顺序固定如下：

1. $U_f^{(l)}$：输入 $d_l$ 行，每行包含 $R$ 个整数；
2. $V_f^{(l)}$：输入 $R$ 行，每行包含 $R$ 个整数；
3. $c_f^{(l)}$：输入 $1$ 行，包含 $R$ 个整数；
4. $U_b^{(l)}$：输入 $d_l$ 行，每行包含 $R$ 个整数；
5. $V_b^{(l)}$：输入 $R$ 行，每行包含 $R$ 个整数；
6. $c_b^{(l)}$：输入 $1$ 行，包含 $R$ 个整数；
7. $p_0^{(l)}$：输入 $1$ 行，包含 $R$ 个整数；
8. $r_{N+1}^{(l)}$：输入 $1$ 行，包含 $R$ 个整数。

全部 $S$ 层双向 RNN 参数之后，依次给出 $A$ 个注意力头的参数。注意力头按照 $h=0,1,\dots,A-1$ 的编号顺序输入，每个头依次包含：

1. $Q_h$：输入 $2R$ 行，每行包含 $Q$ 个整数；
2. $K_h$：输入 $2R$ 行，每行包含 $Q$ 个整数；
3. $V_h$：输入 $2R$ 行，每行包含 $Q$ 个整数。

所有注意力头的参数结束后，剩余参数按照 $W_p$、$c_p$、$W_y$、$c_y$ 的顺序给出：

1. $W_p$：输入 $AQ$ 行，每行包含 $2R$ 个整数；
2. $c_p$：输入 $1$ 行，包含 $2R$ 个整数；
3. $W_y$：输入 $2R$ 行，每行包含 $C$ 个整数；
4. $c_y$：输入 $1$ 行，包含 $C$ 个整数。

所有输入矩阵均按照从上到下、逐行的顺序给出。

输出描述

按照位置 $1,2,\dots,N$ 的顺序输出计算结果，共输出 $N$ 行。

第 $t$ 行包含 $C$ 个非负整数，依次表示最终输出向量 $y_t$ 的各个分量，相邻整数之间使用一个空格分隔。

样例1

输入

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

输出

1

说明

由于 $N=1$，只需计算位置 1。第 1 层正向隐藏状态为 $p_1^{(1)} = (2 \cdot 3 + 4 \cdot 4 + 1) \bmod 5 = 23 \bmod 5 = 3$。 反向隐藏状态为 $r_1^{(1)} = (2 \cdot 2 + 0 \cdot 1 + 3) \bmod 5 = 7 \bmod 5 = 2$。 因此编码器输出 $e_1=[3,2]$。

注意力头中： $q_1 = e_1 Q_0 = 3 \cdot 1 + 2 \cdot 0 = 3$， $k_1 = e_1 K_0 = 3 \cdot 0 + 2 \cdot 1 = 2$， $v_1 = e_1 V_0 = (3 \cdot 4 + 2 \cdot 3) \bmod 5 = 18 \bmod 5 = 3$。 注意力分数 $\beta_{1,1} = q_1 k_1 \bmod 5 = 6 \bmod 5 = 1$，因此注意力输出 $c_1 = 1 \cdot 3 \bmod 5 = 3$。

投影层中 $c_1 W_p = [3 \cdot 1, 3 \cdot 4] \bmod 5 = [3,2]$。 残差连接后 $u_1 = ([3,2]+[2,1]+[3,2]) \bmod 5 = [3,0]$。 输出层计算 $y_1 = (3 \cdot 2 + 0 \cdot 1 + 0) \bmod 5 = 6 \bmod 5 = 1$。

最终输出为 1。

样例2

输入

2 1 1 2 1 1 1 5
1
2
1
0
0
1
0
0
0
0
1
0
0
1
1
0
1 1
0 0
1 0
0 1
0 0

输出

1 1
2 2

说明

第 1 层中正向和反向都只使用当前输入，因此 $p_t^{(1)} = x_t$，$r_t^{(1)} = x_t$。 于是位置 1 的编码器输出为 $e_1=[1,1]$，位置 2 的编码器输出为 $e_2=[2,2]$。

注意力头参数将 $q_t$ 取为 $e_t$ 的第 1 个分量，$k_t$ 取为 $e_t$ 的第 2 个分量，$v_t$ 取为 $e_t$ 的第 1 个分量。 所以 $q_1=1$，$q_2=2$，$k_1=1$，$k_2=2$，$v_1=1$，$v_2=2$。

对于位置 1，注意力分数为 $\beta_{1,1}=1 \cdot 1 \bmod 5=1$， $\beta_{1,2}=1 \cdot 2 \bmod 5=2$。 注意力输出为 $c_1 = (1 \cdot 1 + 2 \cdot 2) \bmod 5 = 5 \bmod 5 = 0$。

对于位置 2，注意力分数为 $\beta_{2,1}=2 \cdot 1 \bmod 5=2$， $\beta_{2,2}=2 \cdot 2 \bmod 5=4$。 注意力输出为 $c_2 = (2 \cdot 1 + 4 \cdot 2) \bmod 5 = 10 \bmod 5 = 0$。

所以两个位置的注意力输出均为 0。残差后 $u_t = e_t$，输出层使用单位矩阵，因此最终输出为位置 1 的 $[1,1]$ 和位置 2 的 $[2,2]$。

样例3

输入

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

输出

2

说明

由于 $N=1$，仍只需计算位置 1。第 1 层正向隐藏状态为 $p_1^{(1)} = (2 \cdot 3 + 4 \cdot 4 + 1) \bmod 5 = 3$。 反向隐藏状态为 $r_1^{(1)} = (2 \cdot 2 + 0 \cdot 1 + 3) \bmod 5 = 2$。 因此编码器输出 $e_1=[3,2]$。

第 0 个头中： $q_1^{(0)} = 3 \cdot 1 + 2 \cdot 0 = 3$， $k_1^{(0)} = 3 \cdot 0 + 2 \cdot 1 = 2$， $v_1^{(0)} = (3 \cdot 4 + 2 \cdot 3) \bmod 5 = 3$。 注意力分数 $\beta_{1,1}^{(0)} = 3 \cdot 2 \bmod 5 = 6 \bmod 5 = 1$， 因此该头输出 $c_1^{(0)} = 1 \cdot 3 = 3$。

第 1 个头中： $q_1^{(1)} = 3 \cdot 0 + 2 \cdot 1 = 2$， $k_1^{(1)} = (3 \cdot 1 + 2 \cdot 2) \bmod 5 = 7 \bmod 5 = 2$， $v_1^{(1)} = (3 \cdot 1 + 2 \cdot 4) \bmod 5 = 11 \bmod 5 = 1$。 注意力分数 $\beta_{1,1}^{(1)} = 2 \cdot 2 \bmod 5 = 4$， 因此该头输出 $c_1^{(1)} = 4 \cdot 1 = 4$。

拼接后注意力输出为 $c_1=[3,4]$。投影矩阵是单位矩阵，所以残差后 $u_1 = ([3,4]+[0,0]+[3,2]) \bmod 5 = [1,1]$。 输出层计算 $y_1 = (1 \cdot 1 + 1 \cdot 1 + 0) \bmod 5 = 2$。

最终输出为 2。