小罐跳舞

题目链接：SSL 1535

题目大意

给你三个矩阵 A,B,C，要你判断 A*B=C 是否成立。

思路

如果直接暴力乘，我们的复杂度是 \(O(n^3)\)，但是我们只允许 \(O(n^2)\) 的。

看看这个 \(n^3\) 如何构成，就是 \(A\) 的 \(n\)，\(B\) 的 \(m\)，\(A\) 的 \(m\)（也就是 \(B\) 的 \(n\)）
那你会发现取决于这三个值，而且后面会保留的是前面两个。
考虑把其中一个变成 \(1\)，但是显然不能直接变，因为你要乘啊，你总得是要乘的。
那你考虑乘完之后变成 \(1\) 出来，然后再跟另一个乘上。
那就相当于用一个 \(A*B*R=C*R\rightarrow A*B=C\)
那你就让 \(R\) 是一个 \(n\times 1\) 的矩阵即可，这个我们可以随机生成。

然后按上面的说法我们就要先乘 \(B*R\)，再带上 \(A\)，但是注意顺序不能错。
然后因为这个随机可能出事，我们得多随机几次重复验证。
（然后我的代码三次就会超时，不过两次也能过，听说一次都能如果随机好的话）

代码

#include<cstdio>
#include<cstdlib>
#define rr register
#define ll long long

using namespace std;

const int N = 1005;
struct matrix {
	ll n, m, a[N][N];
}A, B, C, tmp, R;
int n;

matrix operator *(matrix x, matrix y) {
	matrix re; re.n = x.n; re.m = y.m;
	for (rr int i = 1; i <= re.n; i++) for (rr int j = 1; j <= re.m; j++) re.a[i][j] = 0;
	for (rr int k = 1; k <= x.m; k++)
		for (rr int i = 1; i <= re.n; i++)
			for (rr int j = 1; j <= re.m; j++)
				re.a[i][j] += x.a[i][k] * y.a[k][j];
	return re;
}

bool operator !=(matrix x, matrix y) {
	if (x.n != y.n || x.m != y.m) return 1;
	for (rr int i = 1; i <= x.n; i++)
		for (rr int j = 1; j <= x.m; j++)
			if (x.a[i][j] != y.a[i][j]) return 1;
	return 0;
}

ll re, zf; char c;
ll read() {
	re = 0; zf = 1; c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') zf = -zf; c = getchar();
	}
	while (c >= '0' && c <= '9') {
		re = (re << 3) + (re << 1) + c - '0';
		c = getchar();
	}
	return re * zf;
}

int main() {
	freopen("transform.in", "r", stdin);
	freopen("transform.out", "w", stdout);
	
	srand(19491001);
	while (scanf("%d", &n) != EOF) {
		A.n = A.m = n;
		for (rr int i = 1; i <= n; i++)
			for (rr int j = 1; j <= n; j++)
				A.a[i][j] = read();
		B.n = B.m = n;
		for (rr int i = 1; i <= n; i++)
			for (rr int j = 1; j <= n; j++)
				B.a[i][j] = read();
		C.n = C.m = n;
		for (rr int i = 1; i <= n; i++)
			for (rr int j = 1; j <= n; j++)
				C.a[i][j] = read();
		bool sam = 1;
		for (int tim = 1; tim <= 2; tim++) {
			R.n = n; R.m = 1; for (rr int i = 1; i <= n; i++) R.a[i][1] = rand();
			tmp = B * R; tmp = A * tmp;
			if (tmp != (C * R)) {
				sam = 0; break;
			}
		}
		if (sam) printf("Yes\n");
			else printf("No\n");
	}
	
	return 0;
}