矩阵运算
计算机软件能力认证考试系统
现在这分也越来越难挣咯~这也超时，那也超时的。但是也给我们一个矩阵优化的思路，那就是 同时转置+乘法。下面给出超时和AC。
暴力超时法：70分
#include <iostream>
#include <vector>
using namespace std;
#define ll long longint n,d;//矩阵大小 vector<vector<ll>> Trans(vector<vector<ll>>K) //转置
{vector<vector<ll>>temp(d,vector<ll>(n,0));for(int i=0;i<d;i++)for(int j=0;j<n;j++)temp[i][j]=K[j][i];return temp;} ll Mul_tensor(int row,int col,vector<vector<ll>>Q,vector<vector<ll>>K)
{ll c=0;for(int i=0;i<Q[0].size();i++) c+=Q[row][i]*K[i][col];return c;
}vector<vector<ll>> Mul_matrix(vector<vector<ll>>Q,vector<vector<ll>>K)
{vector<vector<ll>>temp(Q.size(),vector<ll>(K[0].size(),0));for(int i=0;i<Q.size();i++) //取Q的行数 {for(int j=0;j<K[0].size();j++) //K的列数 {temp[i][j]=Mul_tensor(i,j,Q,K);}}return temp;
}int main()
{cin>>n>>d; vector<vector<ll>>Q(n);vector<vector<ll>>K(n);vector<vector<ll>>V(n);int t;for(int i=0;i<n;i++)for(int j=0;j<d;j++){cin>>t;Q[i].push_back(t);} for(int i=0;i<n;i++)for(int j=0;j<d;j++){cin>>t;K[i].push_back(t);} vector<vector<ll>>Kt=Trans(K);vector<vector<ll>>QKt=Mul_matrix(Q,Kt);for(int i=0;i<n;i++)for(int j=0;j<d;j++){cin>>t;V[i].push_back(t);}int w;for(int i=0;i<n;i++){cin>>w;for(int j=0;j<QKt[0].size();j++)QKt[i][j]*=w;}vector<vector<ll>>ans=Mul_matrix(QKt,V);for(int i=0;i<ans.size();i++){for(int j=0;j<ans[0].size();j++)cout<<ans[i][j]<<" ";cout<<endl;}return 0;
}优化：将乘法和转置一起处理
我们发现，当矩阵过大的时候，转置啊乘法啊什么的就会很费事。所以这里我们将转置合并到乘法里面去，同时在乘第二个矩阵的时候也把W乘进去。具体规律我写到了代码中，大家也可以自己手动画画。
AC：
#include <iostream>
#include <vector>
using namespace std;
#define ll long long//答案，优化策略是K一边置换一边乘V const int N=1e4+2;
const int D=22; int n,d;//矩阵大小
int K[N][D],Q[N][D],V[N][D];
int W[N];int main()
{cin>>n>>d; ll temp[D][D]={0};for(int i=0;i<n;i++)for(int j=0;j<d;j++)cin>>Q[i][j];for(int i=0;i<n;i++)for(int j=0;j<d;j++)cin>>K[i][j];for(int i=0;i<n;i++)for(int j=0;j<d;j++)cin>>V[i][j];for(int i=0;i<n;i++) cin>>W[i];//转置和乘V一步到位//例如，C00=A00*B00+A01*B10+A02*B20，假如A是转置后的值，那转置前就是：A00，A10，A20//转化成就是C00= A00*B00+A10*B10+A20*B20// 同理，C01=A00*B01+A01*B11+A02*B21--> C01=A00*B01+A10*B11+A20*B21//总结出规律，我们发现AB都是相同行的值在乘 ： for(int i=0;i<d;i++)for(int j=0;j<d;j++)for(int k=0;k<n;k++)temp[i][j] += K[k][i] * V[k][j]; //相同行匹配 ll ans[N][D]={0};//乘Q乘w一步到位 for(int i=0;i<n;i++){for(int j=0;j<d;j++){for(int k=0;k<d;k++)ans[i][j]+=Q[i][k]*temp[k][j];ans[i][j]*=W[i];}}for(int i=0;i<n;i++){for(int j=0;j<d;j++)cout<<ans[i][j]<<" ";cout<<endl;}return 0;
}
