CCF-CSP第30次认证第二题——矩阵运算
官网链接：TUOJ
时间限制： 5.0 秒
空间限制： 512 MiB
下载题目目录（样例文件）
题目背景
Softmax(𝑄×𝐾𝑇𝑑)×𝑉Softmax(dQ×KT)×V 是 Transformer 中注意力模块的核心算式，其中 𝑄Q、𝐾K 和 𝑉V 均是 𝑛n 行 𝑑d 列的矩阵，𝐾𝑇KT 表示矩阵 𝐾K 的转置，×× 表示矩阵乘法。
题目描述
为了方便计算，顿顿同学将 SoftmaxSoftmax 简化为了点乘一个大小为 𝑛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%70% 的测试数据满足：𝑛≤100n≤100 且 𝑑≤10d≤10；输入矩阵、向量中的元素均为整数，且绝对值均不超过 3030。
全部的测试数据满足：𝑛≤104n≤104 且 𝑑≤20d≤20；输入矩阵、向量中的元素均为整数，且绝对值均不超过 10001000。
提示
请谨慎评估矩阵乘法运算后的数值范围，并使用适当数据类型存储矩阵中的整数。
参考题解
参考思路：刚开始忘记矩阵乘法怎么乘的了，建议碰到类似情况先自己在草稿纸上算一算
#include <iostream>
#include <vector>using namespace std;
/*
3 2
1 2
3 4
5 6
10 10
-20 -20
30 30
6 5
4 3
2 1
4 0 -5
*/
int main () {//读取输入 int n, d;cin >> n >> d;vector<vector<int> > Q(n, vector<int> (d, 0));for(int i = 0; i < n; i++) {for(int j = 0; j < d; j++) {cin >> Q[i][j]; }} vector<vector<int> > K(n, vector<int> (d, 0));for(int i = 0; i < n; i++) {for(int j = 0; j < d; j++) {cin >> K[i][j]; }}vector<vector<int> > V(n, vector<int> (d, 0));for(int i = 0; i < n; i++) {for(int j = 0; j < d; j++) {cin >> V[i][j]; }}vector<int> W(n);for(int i = 0; i < n; i++) {cin >> W[i];}//计算 (Q ×K^T) * Wvector<vector<long long> > result(n, vector<long long> (n, 0));//注意计算方式，可先在草稿纸上自己算一下试试 for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {for(int k = 0; k < d; k++) {result[i][j] += Q[i][k] * K[j][k] * W[i];}}}
// for(int i = 0; i < n; i++) {
// for(int j = 0; j < n; j++) {
// cout << result[i][j] << " ";
// }
// }//计算 result × Vvector<vector<long long> > answer(n, vector<long long> (d, 0));for(int i = 0; i < n; i++) {for(int j = 0; j < d; j++) {for(int k = 0; k < n; k++) {answer[i][j] += result[i][k] * V[k][j]; //注意此处是kj而不是jk，因为一个转置了一个没转置 }}} //输出结果for(int i = 0; i < n; i++) {for(int j = 0; j < d; j++) {cout << answer[i][j] << ' ';}if(i != n - 1) cout << '\n';} return 0;
}
总结
遇到的问题与解决
- 二维数组初始化有误：根本原因是对于vector的使用不熟悉
- vector添加元素用法错误
- 矩阵乘法计算有误导致每次运行结果不同（不过为什么结果会越来越大呢，是不是因为V越界了，下次还是用at()来读数据吧，有越界检查）
果然是因为越界了
相关知识点总结
vector 是 C++ 中的一个动态数组容器，使用起来相对灵活，但也需要注意一些常见的问题。以下是一些 vector 的常用操作和注意事项：
1. 初始化 vector
- 使用大小和初值初始化：
vector<int> v(10, 0); // 创建一个包含 10 个 0 的 vector - 使用初始列表初始化：
vector<int> v = {1, 2, 3}; // 创建一个包含 1, 2, 3 的 vector - 空 vector 初始化：
vector<int> v; // 创建一个空的 vector
2. 访问元素
- 使用
[]访问：v[2] = 10; // 将第三个元素设置为 10 - 使用
at()访问（会进行越界检查）：v.at(2) = 10; // 同样是将第三个元素设置为 10，但如果越界会抛出异常
3. 添加元素
push_back()：在末尾添加元素：v.push_back(5); // 向 vector 添加一个元素 5emplace_back()：在末尾构造一个元素（相比push_back性能稍优）：v.emplace_back(5); // 在末尾直接构造一个元素 5
关键区别：
push_back需要一个已经构造的对象，它会复制或移动对象。emplace_back直接在vector的末尾原地构造对象，避免了不必要的临时对象和复制操作。
4. 删除元素
pop_back()：删除末尾元素：v.pop_back(); // 删除最后一个元素- 使用
erase()删除指定位置的元素：v.erase(v.begin() + 2); // 删除第三个元素
5. 修改 vector 大小
resize()：修改大小（多余的元素会被丢弃，大小不足会用默认值填充）：v.resize(10); // 将 vector 大小调整为 10resize()可以指定新的元素值：v.resize(10, 0); // 调整大小为 10，新增的元素设置为 0
6. 遍历 vector
- 使用传统的
for循环：for (int i = 0; i < v.size(); i++) {cout << v[i] << " "; } - 使用范围
for循环：for (auto& val : v) {cout << val << " "; }
7. 获取 vector 的大小
size()：返回元素个数：int size = v.size();empty()：检查vector是否为空：if (v.empty()) {cout << "vector is empty"; }
8. 多维 vector
- 声明二维
vector：vector<vector<int>> matrix(n, vector<int>(d, 0)); // 创建 n 行 d 列的二维 vector，元素初始值为 0
9. 注意事项
vector使用的是动态内存管理，因此操作如push_back()和resize()可能导致重新分配内存，影响性能。在大量操作时，最好预先设置好capacity()，避免不必要的内存重分配：vector<int> v; v.reserve(1000); // 预留足够的空间vector的size()和capacity()是两个不同的概念，size()是当前元素的个数，capacity()是为元素分配的内存大小。cout << "Size: " << v.size() << " Capacity: " << v.capacity() << endl;
10. 总结
vector是一个非常方便的容器，使用时需要注意大小和越界访问，尤其是在进行动态增删操作时。- 需要根据需求选择正确的访问方式，避免不必要的性能损耗，例如，尽量避免频繁使用
push_back()而不预分配空间。
