3318 Matrix Multiplication

問題概要

n次正方行列A,B,Cが与えられる。
A×B=Cが成り立っているかを判定せよ。

n≦500,A,Bの各成分は絶対値100以下、Cの各成分の絶対値は10億以下とする。

解法

問題文中の警告にあるようにO(n^3)でやるとTLE.（どんだけテストデータ膨大なんだ）

B,Cの各行ベクトルごとにrolling hashを計算した列ベクトルをl,rとすれば、
Al=rとなっているはずなので、rolling hashの基数を2通りくらい試して、両方で答えが合っているかを見てやる。

rolling hashは文字列一致や回文判定のときによく使うハッシュで、
b0,b1,b2,...bn-1を進数と見た値である。すなわち、
b0*h^n-1 + b1*h^n-2 + …… + b1*1

ソースコード

int n,A[500][500],B[500][500],C[500][500];
int l[500],r[500];

bool ck(int w){
	rep(i,n){
		l[i]=r[i]=0;
		rep(j,n){
			l[i]*=w; l[i]+=B[i][j];
			r[i]*=w; r[i]+=C[i][j];
		}
	}
	rep(i,n){
		rep(j,n)r[i]-=A[i][j]*l[j];
		if(r[i])return 0;
	}
	return 1;
}
int main(){
	scanf("%d",&n);
	rep(i,n)rep(j,n)scanf("%d",A[i]+j);
	rep(i,n)rep(j,n)scanf("%d",B[i]+j);
	rep(i,n)rep(j,n)scanf("%d",C[i]+j);
	
	puts(ck(101)&&ck(103)?"YES":"NO");
	return 0;
}