POJ 3213 矩阵乘法（优化）

思路：

1.暴力出奇迹 n=1000 n^3矩阵乘法竟然能卡过。。。（Tips：不要乱写读入优化，这玩意儿加了超时，不加AC……）

2.

注意题目中的“最多只能有一个地方不一样，，”

我就想到了 能不能用一行的和来优化一下。。一次算一行

我们可以手动模拟一下。。 发现了一个规律……

（本人的草稿纸…… 略乱）



我就模拟了一下答案的第一行。。

发现：

先统计一个sumb[i] +=a[i][j]（1<=j<=M）

这个是B数组第i行前M个数的和

sumc[i]是C数组第i行的和

a[i][j]*sumb[j]应该等于sumc[i] （不信的话你可以手动模拟啊~）

这样子是n^2的复杂度

如果不等于sumc[i]的话 就做一遍一行的矩阵乘法就OK了。。

整体复杂度 O (n^2)

简单的矩阵乘法。。（是不是很短）

//By SiriusRen

#include <cstdio>

using namespace std;

#define s 1005

#define ff(x,y) for(int i=1;i<=x;i++)for(int j=1;j<=y;j++)

int N,P,M,a[s][s],b[s][s],c[s][s],ans[s][s];

int main(){

    scanf("%d%d%d",&N,&P,&M);

    ff(N,P)scanf("%d",&a[i][j]);

    ff(P,M)scanf("%d",&b[i][j]);

    ff(N,M)scanf("%d",&c[i][j]);

    ff(N,M)for(int k=1;k<=P;k++)ans[i][j]+=a[i][k]*b[k][j];

    ff(N,M)if(ans[i][j]!=c[i][j]){printf("No\n%d %d\n%d",i,j,ans[i][j]);return 0;}

    printf("Yes");

}

这是加了优化的

//By SiriusRen

#include <cstdio>

using namespace std;

#define siz 1005

int N,P,M,a[siz][siz],b[siz][siz],c[siz][siz],jy[siz],sumb[siz],sumc[siz];

signed main(){

    scanf("%d%d%d",&N,&P,&M);

    for(int i=1;i<=N;i++)

        for(int j=1;j<=P;j++)

            scanf("%d",&a[i][j]);

    for(int i=1;i<=P;i++)

        for(int j=1;j<=M;j++){

            scanf("%d",&b[i][j]);

            if(j<=M)sumb[i]+=b[i][j];

        }

    for(int i=1;i<=N;i++)

        for(int j=1;j<=M;j++)

            scanf("%d",&c[i][j]),sumc[i]+=c[i][j];

    for(int i=1;i<=N;i++){

        int temp=0;

        for(int j=1;j<=P;j++)

            temp+=a[i][j]*sumb[j];

        if(temp!=sumc[i]){

            for(int j=1;j<=M;j++){

                for(int k=1;k<=P;k++)

                    jy[j]+=a[i][k]*b[k][j];

                if(jy[j]!=c[i][j])

                    printf("No\n%d %d\n%d",i,j,jy[j]);

            }

            return 0;

        }

    }

    puts("Yes");

}