5
24
2016
0

[BZOJ2396] 神奇的矩阵

暴力矩阵乘法显然会TLE。

那么我们随机一个1*n的矩阵D,然后利用矩阵运算的结合律$A*B*D=A*(B*D)$,然后就可以快速判断了。

这样操作完错误率是很低的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
   
const int N=1005;
   
struct Matrix{
int Mt[N][N];
}A,B,C;
   
int n,Tp1[N],Tp2[N];
   
void Mul(int *r,Matrix T){
int Tp[N];
for(int i=1;i<=n;i++){
    Tp[i]=0;
    for(int j=1;j<=n;j++){
        Tp[i]+=r[j]*T.Mt[j][i];
    }
}
for(int i=1;i<=n;i++)r[i]=Tp[i];
}
   
int main(){
freopen("2396.in","r",stdin);
freopen("2396.out","w",stdout);
srand(233);
while(scanf("%d",&n)!=EOF){
    for(int i=1;i<=n;i++)Tp1[i]=Tp2[i]=rand();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&A.Mt[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&B.Mt[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&C.Mt[i][j]);
        }
    }
    Mul(Tp1,A);
    Mul(Tp1,B);
    Mul(Tp2,C);
    int flag=1;
    for(int i=1;i<=n;i++)if(Tp1[i]!=Tp2[i]){flag=0;break;}
    puts(flag?"Yes":"No");
}
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 527

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com