PKU 3213 PM 3

問題

行列A, B, Cが与えられる。
A x B = Cになっているかどうかを検算せよ。

なっている場合はYes, そうでない場合はNoと、
Cの間違っている成分の行、列およびその成分の正しい値を出力せよ。
Cの成分は高々一つしか間違っていない。

制約条件

Aの行数, Aの列数≦1000
Bの行数, Bの列数≦1000
Cの行数, Cの列数≦1000

方針

ランダムな列ベクトルxを取って、
A(Bx) = Cxが成り立っているかを見れば、O(N^2)時間で行列積の検算ができる。

ソースコード

int A[1000][1000], B[1000][1000], C[1000][1000];
ll x[1000], xc[1000], xa[1000], xb[1000];
int n, p, m;

int main(){
	scanf("%d%d%d", &n, &p, &m);
	rep(i, n) rep(j, p) scanf("%d", A[i] + j);
	rep(i, p) rep(j, m) scanf("%d", B[i] + j);
	rep(i, n) rep(j, m) scanf("%d", C[i] + j);
	
	rep(i, m) x[i] = rand();
	rep(i, n) rep(j, m) xc[i] += C[i][j] * x[j];
	rep(i, p) rep(j, m) xb[i] += B[i][j] * x[j];
	rep(i, n) rep(j, p) xa[i] += A[i][j] * xb[j];
	
	rep(i, n) if(xa[i] != xc[i]){
		rep(c, m){
			ll a = 0;
			rep(r, p) a += A[i][r] * B[r][c];
			if(a != C[i][c]){
				cout << "No" << endl;
				cout << i + 1 << " " << c + 1 << endl;
				cout << a << endl;
			}
		}
		goto END;
	}
	cout << "Yes" << endl;
	END:;
	
	return 0;
}