KUPC2012 Practice : D - A mul B Problem

最後の問題は少し難しい問題を突っ込んできた。
http://kupc2012pr.contest.atcoder.jp/tasks/kupc2012pr_4

問題

整数Nと、N*Nの行列A,B,Cが与えられる。
A*B=Cかどうかを判定せよ。

解法

N<=1000なので、普通に掛け算してO(N^3)ではTLE。
多少高速な乗算法を使ってもO(N^2.4)程度かかるので難しそう。

そこでEditorialを参考にして解いた。
各要素0と1からランダムに選んで作成したN次元ベクトルrに対し、かどうかを判定する。
一致すれば、の確率で結果は正しい。理由はEditorial参照。
１回あたりの検証処理はO(N^2)で済む。
念のため、時間いっぱいまで色んなrを繰り返し試す。

int N;
ll A[1001][1001],B[1001][1001],C[1001][1001];

int check(int y,int x) {
	ll r=0;
	int i;
	FOR(i,N) r+=A[y][i]*B[i][x];
	return r==C[y][x];
}

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	
	N=GETi();
	FOR(y,N) FOR(x,N) A[y][x]=GETi();
	FOR(y,N) FOR(x,N) B[y][x]=GETi();
	FOR(y,N) FOR(x,N) C[y][x]=GETi();
	
	if(N>100) {
		struct timeval tv1,tv2;
		gettimeofday(&tv1,NULL);
		while(1) {
			gettimeofday(&tv2,NULL);
			if((tv2.tv_sec-tv1.tv_sec)*1000000+(tv2.tv_usec-tv1.tv_usec)>4000000) break;
			ll r[1001],r2[1001],r3[1001];
			FOR(i,N) r[i]=r2[i]=rand()%2;
			// Br
			FOR(y,N) {
				r3[y]=0;
				FOR(x,N) r3[y]+=r[x]*B[y][x];
			}
			// Ar
			FOR(y,N) {
				r[y]=0;
				FOR(x,N) r[y]+=r3[x]*A[y][x];
			}
			// Cr
			FOR(y,N) {
				r3[y]=0;
				FOR(x,N) r3[y]+=r2[x]*C[y][x];
				if(r3[y]!=r[y]) return (void)_P("NO\n");
			}
		}
	}
	else {
		FOR(y,N) FOR(x,N) if(check(y,x)==0) return (void)_P("NO\n");
	}
	return (void)_P("YES\n");
}

まとめ

これは知らないと難しいな。でも面白いアルゴリズムだ。