【SSL 1535】小罐跳舞（构造）

小罐跳舞

题目链接：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\ast B\ast R=C\ast R\to A\ast B=C$
那你就让 $R$ 是一个 $n\times 1$ 的矩阵即可，这个我们可以随机生成。

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

代码

#include
#include
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76