CCF-CSP-第30次2023.052_矩阵运算_C暴力破解矩阵相乘
CCF CSP 第30次（2023.05）（2_矩阵运算_C++）（暴力破解）(矩阵相乘)
时间限制 ： 5.0s
空间限制 ： 512.0MB
题目背景：
Softmax(Q×K T /√d)×V 是 Transformer 中注意力模块的核心算式，其中 Q、K 和 V 均是 n 行 d 列的矩阵，K T 表示矩阵 K 的转置，× 表示矩阵乘法。
题目描述：
为了方便计算，顿顿同学将 Softmax 简化为了点乘一个大小为 n 的一维向量 W：
(W⋅(Q×K T ))×V
点乘即对应位相乘，记 W (i) 为向量 W 的第 i 个元素，即将 (Q×K T ) 第 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 ≤ 10 4 且 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 d
K.resize(n, vector<int>(d)); // 初始化 K 矩阵，大小为 n x d
V.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 n
vector<vector<int>> KT(d, vector<int>(n)); // 初始化转置矩阵 KT，大小为 d x n
for (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 的矩阵 QKT
vector<vector<int>> QKT(n, vector<int>(n, 0)); // 初始化 QKT 矩阵，大小为 n x n，初始值为 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 中
}
}
}
// 计算 W 点乘 QKT，得到 WQKT 矩阵
vector<vector<int>> WQKT(n, vector<int>(n, 0)); // 初始化 WQKT 矩阵，大小为 n x n，初始值为 0
for (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，得到最终的结果矩阵 ans
vector<vector<int>> ans(n, vector<int>(d, 0)); // 初始化 ans 矩阵，大小为 n x d，初始值为 0
for (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 中
}
}
}
// 输出最终结果矩阵 ans
for (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 个元素相乘再相加。
欢迎大家和我沟通交流(✿◠‿◠)