CCF CSP 第30次（2023.05）（2_矩阵运算_C++）
- 题目背景：
- 题目描述：
- 输入格式：
- 输出格式：
- 样例输入
- 样例输出：
- 样例解释：
- 子任务：
- 提示：
- 解题思路：
- 思路一（暴力破解）：
- 代码实现
- 代码实现：
- 部分代码解读
时间限制： 5.0s
空间限制： 512.0MB
题目背景：
Softmax(Q×KT/√d)×V 是 Transformer 中注意力模块的核心算式，其中 Q、K 和 V 均是 n 行 d 列的矩阵，KT 表示矩阵 K 的转置，× 表示矩阵乘法。
题目描述：
为了方便计算，顿顿同学将 Softmax 简化为了点乘一个大小为 n 的一维向量 W：
(W⋅(Q×KT))×V
点乘即对应位相乘，记 W(i) 为向量 W 的第 i 个元素，即将 (Q×KT) 第 i 行中的每个元素都与 W(i) 相乘。
现给出矩阵 Q、K 和 V 和向量 W，试计算顿顿按简化的算式计算的结果。
输入格式：
从标准输入读入数据。
输入的第一行包含空格分隔的两个正整数 n 和 d，表示矩阵的大小。
接下来依次输入矩阵 Q、K 和 V。每个矩阵输入 n 行，每行包含空格分隔的 d 个整数，其中第 i 行的第 j 个数对应矩阵的第 i 行、第 j 列。
最后一行输入 n 个整数，表示向量 W。
输出格式：
输出到标准输出中。
输出共 n 行，每行包含空格分隔的 d 个整数，表示计算的结果。
样例输入
3 2
1 2
3 4
5 6
10 10
-20 -20
30 30
6 5
4 3
2 1
4 0 -5
样例输出：
480 240
0 0
-2200 -1100
样例解释：
子任务：
70 %的测试数据满足：n ≤ 100 且 d ≤ 10；输入矩阵、向量中的元素均为整数，且绝对值均不超过 30。
全部的测试数据满足：n ≤ 104且 d ≤ 20；输入矩阵、向量中的元素均为整数，且绝对值均不超过 1000。
提示：
请谨慎评估矩阵乘法运算后的数值范围，并使用适当数据类型存储矩阵中的整数。
解题思路：
思路一（暴力破解）：
1、解题步骤拆分：
① 数据输入：
- 第一行n d (整数：表示矩阵的大小)
- 输入三个矩阵(分别为Q、K、V（使用二维vector来存储）)，每个矩阵输入 n 行，每行d个整数(空格分隔)。三层循环。
- 最后一行输入 n 个整数代表W(使用一维vector来存储)。
② 数据处理： 计算K的转置。计算Q×K的转置，存储在一个二维vector（QKT）中。再计算W 点乘QKT得二维vector（WQKT）。再计算WQKT×V得答案二维vector（ans）。
③ 答案输出： 输出ans得结果。
代码实现
代码实现：
#include<iostream>
#include<vector>
using namespace std;int main(int argc, char const *argv[])
{int n, d;cin >> n >> d; // 读入矩阵的维度 n（行数）和 d（列数）// 创建 Q、K 和 V 矩阵，初始化为 n 行 d 列的二维向量vector<vector<int>> Q, K, V;Q.resize(n, vector<int>(d)); // 初始化 Q 矩阵，大小为 n x dK.resize(n, vector<int>(d)); // 初始化 K 矩阵，大小为 n x dV.resize(n, vector<int>(d)); // 初始化 V 矩阵，大小为 n x d// 输入 Q 矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < d; j++) {cin >> Q[i][j]; // 读取 Q 矩阵的每个元素}}// 输入 K 矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < d; j++) {cin >> K[i][j]; // 读取 K 矩阵的每个元素}}// 输入 V 矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < d; j++) {cin >> V[i][j]; // 读取 V 矩阵的每个元素}}// 输入 W 向量vector<int> W(n); // 创建一个大小为 n 的 W 向量for (int i = 0; i < n; i++) {cin >> W[i]; // 读取 W 向量的每个元素}// 计算 K 的转置矩阵 KT，大小为 d x nvector<vector<int>> KT(d, vector<int>(n)); // 初始化转置矩阵 KT，大小为 d x nfor (int i = 0; i < n; i++) { // 遍历 K 矩阵for (int j = 0; j < d; j++) {KT[j][i] = K[i][j]; // 将 K 的元素转置到 KT 中}}// 计算 Q × KT，得到一个 n x n 的矩阵 QKTvector<vector<int>> QKT(n, vector<int>(n, 0)); // 初始化 QKT 矩阵，大小为 n x n，初始值为 0for (int i = 0; i < n; i++) { // 遍历 Q 矩阵的每一行for (int j = 0; j < n; j++) { // 遍历 KT 矩阵的每一列for (int k = 0; k < d; k++) { // 遍历 Q 矩阵的列和 KT 矩阵的行QKT[i][j] += Q[i][k] * KT[k][j]; // 计算 Q × KT 的点乘，结果存储在 QKT 中}}}// 计算 W 点乘 QKT，得到 WQKT 矩阵vector<vector<int>> WQKT(n, vector<int>(n, 0)); // 初始化 WQKT 矩阵，大小为 n x n，初始值为 0for (int i = 0; i < n; i++) { // 遍历 W 向量和 QKT 矩阵的每一行for (int j = 0; j < n; j++) {WQKT[i][j] = W[i] * QKT[i][j]; // 用 W 向量的第 i 个元素对 QKT 的第 i 行加权}}// 计算 WQKT × V，得到最终的结果矩阵 ansvector<vector<int>> ans(n, vector<int>(d, 0)); // 初始化 ans 矩阵，大小为 n x d，初始值为 0for (int i = 0; i < n; i++) { // 遍历 WQKT 矩阵的每一行for (int j = 0; j < d; j++) { // 遍历 V 矩阵的每一列for (int k = 0; k < n; k++) { // 遍历 WQKT 矩阵的每一列和 V 矩阵的行ans[i][j] += WQKT[i][k] * V[k][j]; // 计算 WQKT × V 的矩阵乘法，结果存储在 ans 中}}}// 输出最终结果矩阵 ansfor (int i = 0; i < n; i++) {for (int j = 0; j < d; j++) {cout << ans[i][j]; // 输出 ans 矩阵的每个元素if (j != d - 1) { // 如果不是行末尾，则输出空格cout << " ";}}cout << endl; // 输出每行结果后换行}return 0; // 程序正常结束
}
部分代码解读
矩阵相乘
for (int i = 0; i < n; i++) { // 遍历 Q 矩阵的每一行for (int j = 0; j < n; j++) { // 遍历 KT 矩阵的每一列for (int k = 0; k < d; k++) { // 遍历 Q 矩阵的列和 KT 矩阵的行QKT[i][j] += Q[i][k] * KT[k][j]; // 计算 Q × KT 的点乘，结果存储在 QKT 中}}}
注意这里是 QKT[i][j] += Q[i][k] * KT[k][j];
i 行中的 d 个元素分别与 j 列中的 d 个元素相乘再相加。
欢迎大家和我沟通交流(✿◠‿◠)
)
