#P5312. 第3题-多头注意力双向整数RNN
-
1000ms
Tried: 15
Accepted: 12
Difficulty: 8
所属公司 :
华为
时间 :2026年8月26日-AI方向
第3题-多头注意力双向整数RNN
解题思路
本题没有复杂的模型训练过程，只需要严格按照题目给出的公式完成一次前向计算，整体采用模拟算法和矩阵乘法。
首先处理 S 层双向循环网络。对于每一层，正向状态按照 1→N 的顺序递推，反向状态按照 N→1 的顺序递推。每个位置分别计算输入向量与输入权重的乘积、上一状态与循环权重的乘积，再加上偏置并对 MOD 取模，最后将正向和反向状态拼接，作为下一层的输入。
完成 S 层编码后得到每个位置的 2R 维向量 et。
接着计算 A 个注意力头。对于每个头，先由 et 分别计算查询向量、键向量和值向量，再枚举位置 t 和 s，通过点积得到注意力分数，并使用该分数对所有值向量进行加权求和。题目明确不需要使用缩放、softmax 或 mask，因此直接按照公式计算并取模即可。
题目内容
给定一个由多层双向循环神经网络和多头自注意力组成的网络，需要按照给定参数完成一次前向计算。整个计算过程均在模 MOD 的整数域中进行。
网络依次包含多层双向 RNN 编码、多头自注意力、残差连接和线性输出四个部分。
设输入序列长度为 N，每个位置的原始输入向量为 xt。
1. 多层双向 RNN 编码
网络共有 S 层双向 RNN。
记第 l 层在位置 t 的输入为 at(l)，其中：
at(1)=xt第 l 层的输入维度记为 dl：
dl={F,l=1 2R,l>1其中 F 为原始输入维度，R 为单个方向的隐藏状态维度。
对于第 l 层，正向状态按照 t=1,2,…,N 的顺序计算：
pt(l)=(at(l)Uf(l)+pt−1(l)Vf(l)+cf(l))modMOD反向状态按照 t=N,N−1,…,1 的顺序计算：
rt(l)=(at(l)Ub(l)+rt+1(l)Vb(l)+cb(l))modMOD其中 p0(l) 和 rN+1(l) 为该层给定的初始状态。
将两个方向的结果首尾拼接，作为下一层的输入：
at(l+1)=[pt(l)∥rt(l)]因此，当 l<S 时，下一层输入向量的维度为 2R。
完成全部 S 层计算后，定义：
et=[pt(S)∥rt(S)]显然：
et∈ZMOD2R第 l 层使用的参数规模如下：
| 矩阵 | 规模 |
|---|---|
| Uf(l) | dl×R |
| Vf(l) | R×R |
| cf(l) | 1×R |
| Ub(l) | dl×R |
| Vb(l) | R×R |
| cb(l) | 1×R |
| p0(l) | |
| rN+1(l) |
2. 多头自注意力
编码结果 et 进入一个包含 A 个注意力头的多头自注意力模块，每个头的维度为 Q。
本题中的注意力为未归一化的点积注意力，不进行缩放、不使用 softmax，也不存在 mask。
对于第 h 个注意力头，其中 h=0,1,…,A−1，首先计算：
qt(h)=etQhmodMOD kt(h)=etKhmodMOD vt(h)=etVhmodMOD其中：
qt(h),kt(h),vt(h)∈ZMODQ位置 t 对位置 s 的注意力分数定义为：
βt,s(h)=(j=0∑Q−1qt(h)[j]⋅ks(h)[j])modMOD随后计算该注意力头在位置 t 的输出：
ct(h)[j]=(s=1∑Nβt,s(h)⋅vs(h)[j])modMOD其中：
j=0,1,…,Q−1将全部 A 个注意力头的结果按照编号从小到大依次拼接：
ct=[ct(0)∥ct(1)∥⋯∥ct(A−1)]因此：
ct∈ZMODAQ每个注意力头的参数规模如下：
| 矩阵 | 规模 |
|---|---|
| Qh | 2R×Q |
| Kh | |
| Vh |
3. 残差连接
将所有注意力头的输出拼接后，通过投影矩阵映射回 2R 维，并与编码器输出 et 进行残差相加：
ut=(ctWp+cp+et)modMOD其中：
| 矩阵 | 规模 |
|---|---|
| Wp | AQ×2R |
| cp | 1×2R |
4. 输出层
最后通过线性层得到位置 t 的最终输出：
yt=(utWy+cy)modMOD其中：
| 矩阵 | 规模 |
|---|---|
| Wy | 2R×C |
| cy | 1×C |
最终：
yt∈ZMODC题目中的所有向量均视为行向量，矩阵乘法按照“行向量乘矩阵”的方式进行。
所有输入参数均为满足 0≤x<MOD 的非负整数。每次完成向量加法、点积或矩阵乘法后，都需要对结果取模 MOD。
输入描述
第一行输入八个整数 N、F、R、C、S、A、Q、MOD，分别表示序列长度、输入维度、单向隐藏状态维度、输出维度、双向 RNN 层数、注意力头数量、每个注意力头的维度以及模数。
数据范围：
1≤N≤10，1≤F≤5，1≤R≤5，
1≤C≤5，1≤S≤3，1≤A≤4，1≤Q≤4，
2≤MOD≤97。
接下来输入 N 行，每行输入 F 个整数，表示原始输入序列中的一个向量 xt。
随后依次输入 S 层双向 RNN 的参数。
对于第 l 层，令：
dl={F,l=1 2R,l>1按照以下顺序输入：
- Uf(l)：dl 行，每行 R 个整数；
- Vf(l)：R 行，每行 R 个整数；
- cf(l)：1 行，共 R 个整数；
- Ub(l)：dl 行，每行 R 个整数；
- Vb(l)：R 行，每行 R 个整数；
- cb(l)：1 行，共 R 个整数；
- p0(l)：1 行，共 R 个整数；
- rN+1(l)：1 行，共 R 个整数。
接下来依次输入 A 个注意力头的参数。
对于每个注意力头，按照以下顺序输入：
- Qh：2R 行，每行 Q 个整数；
- Kh：2R 行，每行 Q 个整数；
- Vh：2R 行，每行 Q 个整数。
最后依次输入投影层和输出层参数：
- Wp：AQ 行，每行 2R 个整数；
- cp：1 行，共 2R 个整数；
- Wy：2R 行，每行 C 个整数；
- cy：1 行，共 C 个整数。
所有输入的矩阵均按照从上到下、逐行的顺序给出。
输出描述
输出共 N 行。
第 t 行输出 C 个非负整数，表示位置 t 对应的最终输出向量 yt，相邻整数之间使用一个空格分隔。
样例1
输入
2 1 1 1 1 1 1 11
1
2
1
1
0
1
1
0
0
0
1
0
1
0
1
0
1 0
0 0
1
1
0
输出
3
2
说明
本样例只有 1 层双向 RNN 和 1 个注意力头。
双向 RNN 编码后：
e1=[1,3],e2=[3,2]注意力模块得到：
c1=[10],c2=[8]经过投影和残差连接后：
u1=[0,3],u2=[0,2]因此最终输出为 3 和 2。