时间限制： 5.0 秒
空间限制： 512 MiB
题目背景
Softmax(Q×KTd)×VSoftmax(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 个整数，其中第 ii 行的第 jj 个数对应矩阵的第 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。
提示
请谨慎评估矩阵乘法运算后的数值范围，并使用适当数据类型存储矩阵中的整数。
思路
关键在于对矩阵计算的理解，转置，点乘，叉乘，以及运算顺序的调整
假设两个矩阵，分别为a行b列与b行c列，那么一次矩阵运算复杂度是a乘以c乘以b，对于这题，如果从左往右运算复杂度将会到
1e4乘以1e4乘以20>1e9 (n=1e4,d=20)，常识来讲1e8以上的复杂度就已经很危险了，超时也很正常从右往左算的话，注意到K之前是n行b列，转置后是b行n列，与后面的V(n行b列)运算后可以得到b行b列的式子，非常舒服。
这道题想要ac，只能从右往左算，
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll K[21][10001], V[10001][21], Q[10001][21], W[10001], ans[10001][21];
ll KV[21][21];
int main()
{
int n, d;
cin >> n >> d;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= d; j++)
cin >> Q[i][j];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= d; j++)
cin >> K[j][i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= d; j++)
cin >> V[i][j];
for (int i = 1; i <= n; i++)
cin >> W[i];
// 先计算KT(dxn) Ｘ Ｖ(nxd)
for (int i = 1; i <= d; i++)
{
for (int k = 1; k <= n; k++)
{
int tmp = K[i][k];
for (int j = 1; j <= d; j++)
{
KV[i][j] += tmp * V[k][j];
}
}
}
// Q(nXd) X KV(dxd)
for (int i = 1; i <= n; i++)
{
for (int k = 1; k <= d; k++)
{
int tmp = Q[i][k];
for (int j = 1; j <= d; j++)
{
ans[i][j] += tmp * KV[k][j];
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= d; j++)
{
ans[i][j] *= W[i];
cout << ans[i][j] << " ";
}
cout << endl;
}
}