AcWing 5082. 矩阵运算
原题链接
简单
作者:
Kingah
,
2023-11-17 18:32:59
,
所有人可见
,
阅读 104
#include <bits/stdc++.h>
using namespace std;
const int N = 110, D = 15;
// 一定要开LL,不开LL见祖宗(笑hh
typedef long long LL;
#define VVL vector<vector<LL>>
int n, d;
// 矩阵乘法,时间复杂度为O(nmt)
VVL mul(VVL &a, VVL &b)
{
int n = a.size(), m = b[0].size(), t = b.size();
VVL c = VVL(n, vector<LL>(m));
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
for (int k = 0; k < t; k ++)
c[i][j] += a[i][k] * b[k][j];
return c;
}
void print(VVL &t)
{
for (int i = 0; i < t.size(); i ++)
{
for (int j = 0; j < t[0].size(); j ++)
cout << t[i][j] << ' ';
cout << endl;
}
}
int main()
{
cin >> n >> d;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
VVL q = VVL(n, vector<LL>(d)),
k = VVL(n, vector<LL>(d)),
v = VVL(n, vector<LL>(d)),
kt = VVL(d, vector<LL>(n));
vector<LL> w(n);
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];
for (int i = 0; i < n; i ++)
for (int j = 0; j < d; j ++)
kt[j][i] = k[i][j];
// 矩阵乘法有结合律,通过这个来降低时间复杂度
// 已知Q[n,d] KT[d,n] V[n,d]
// 从左往右算时间复杂度为O(d * n^2) 大概为1e9
// 从右往左算时间复杂度为O(n * d^2) 大概为4e6
VVL t = mul(kt, v);
t = mul(q, t);
for (int i = 0; i < t.size(); i ++)
for (int j = 0; j < t[0].size(); j ++)
t[i][j] *= w[i];
print(t);
return 0;
}