3318:Matrix Multiplication

keyword

行列　C++

概要

サイズ500以下の正方行列A,B,Cが与えられる。AB = Cが成り立つかどうか調べる問題。
合宿のときに何か話してるのを聞いた気がする。行列の積は順序を入れ替えるだけで早くなるらしい。2次元配列を舐めるとき縦に走るより横に走った方が速いのと同じ理屈。大半のプログラムの実速はメモリと聞いた。というわけで何の工夫もせずO(N^3)で通した。自作のreadintも役に立ったのかもしれない。

int main(){
    int a[500][500], b[500][500], c[500][500];
    int n;

    n = readint();

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            a[i][j] = readint();

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            b[i][j] = readint();

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            c[i][j] = readint();

    for(int i=0; i<n; i++)
        for(int k=0; k<n; k++)
            for(int j=0; j<n; j++)
                c[i][j] -= a[i][k]*b[k][j];

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(c[i][j]){
                printf("NO\n");
                return 0;
            }

    printf("YES\n");

    return 0;
}