矩阵 A×B

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1183 字

输入n×m的矩阵A与m×p的矩阵B，输出乘积

一本通
例

正文

/*
原题：T1641「一本通 6.5 例 1」矩阵 A×B
题意：输入 n×m 的矩阵 A 与 m×p 的矩阵 B，输出乘积矩阵 C=A×B。
思路：按矩阵乘法定义三重循环累加，C[i][j]=ΣA[i][k]·B[k][j]。
循环顺序取 i,k,j 可直接累加到 C，无需单独清零，也更利用缓存局部性。
复杂度：时间 O(n·m·p)，空间 O(n·p)
易错点：1) 读入顺序是 A(n 行 m 列)、再一个整数 p、再 B(m 行 p 列)，别把 p 误当行数；
2) 累加器用 long long，避免 int 乘法中间结果溢出；
3) 每行内用空格分隔、行末不留多余空格。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<vector<long long>> a(n,vector<long long>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    int p;
    cin>>p;
    vector<vector<long long>> b(m,vector<long long>(p));
    for(int i=0;i<m;i++){
        for(int j=0;j<p;j++){
            cin>>b[i][j];
        }
    }
    vector<vector<long long>> c(n,vector<long long>(p,0));
    for(int i=0;i<n;i++){
        for(int k=0;k<m;k++){
            for(int j=0;j<p;j++){
                c[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<p;j++){
            if(j>0){
                cout<<" ";
            }
            cout<<c[i][j];
        }
        cout<<"\n";
    }
    return 0;
}

矩阵 A×B

正文

一本通·提高篇的其它内容