poj 3318 Matrix Multiplication 随机化算法之舍伍德算法

缘起

无聊, 研究一下随机化算法. poj 3318 Matrix Multiplication

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
给定你3个n阶方阵 A,B,C, 问你 A*B=C是否成立?

【输入】
只需要处理一组数据, 第一行是n（n ≤ 500）, 然后是三个n阶方阵. A，B的数的绝对值<100
C的矩阵的绝对值<=1000w

【输出】
YES或者NO

【样例输入】
2
1 0
2 3
5 1
0 8
5 1
10 26

【样例输出】
YES

【限制】
2s

显然, 老老实实的矩阵相乘再比较的话, 复杂度是O(n^3)的. 会被T掉（500^3=125000000, 过亿了）.

所以本题需要使用舍伍德算法.

即随机的挑选3w次, 每次随机挑选一行一列, 然后计算A*B 的此行此列的元素（复杂度是On）. 看看是不是和C的此行此列相等. 只要一次不相等, return false. 如果通过了3w次测试的话, 那A*B基本就肯定和C是相等了.

复杂度降低为 3w*500=1500w. 这个复杂度是可以在2s内完成的.

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
77
78
79
80
81
82
83
84
85
86
87
88
//#include "stdafx.h"
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <ctype.h>
//#define LOCAL

const int maxn = 505;
int n, a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];

void read(int &x)
{
	x = 0;
	int f = 1;
	char c = getchar();
	while(!isdigit(c))
	{
		if (c=='-')
		{
			f = -1;
		}
		c = getchar();
	}
	while(isdigit(c))
	{
		x = (x<<3)+(x<<1)+(c^48);
		c = getchar();
	}
	x*=f;
}

bool sherwood() // 舍伍德随机化算法
{
	for (int kase = 0,col,row; kase<30000; kase++) // 随机测试3w次
	{
		row = rand()%n+1;
		col = rand()%n+1; // 随机测试A*B的row行、col列和c[row][col]是否相等
		int ans = 0;
		for (int i = 1; i<=n; i++)
		{
			ans+=a[row][i]*b[i][col];
		}
		if (ans!=c[row][col])
		{
			return false;
		}
	}
	return true; // 通过了3w次随机测试, 可以认为A*B和C相等的可能性近乎100%
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	srand((int)time(0));
	read(n);
	for (int i = 1;i<=n; i++)
	{
		for (int j = 1;j<=n; j++)
		{
			read(a[i][j]);
		}
	}
	for (int i = 1;i<=n; i++)
	{
		for (int j = 1;j<=n; j++)
		{
			read(b[i][j]);
		}
	}
	for (int i = 1;i<=n; i++)
	{
		for (int j = 1;j<=n; j++)
		{
			read(c[i][j]);
		}
	}
	if (sherwood())
	{
		puts("YES");
	}
	else
	{
		puts("NO");
	}
	return 0;
}

注意，用C++提交 ac, 用G++ 提交会RE

ac情况（真他么险!）

Status Accepted
Time 1985ms
Memory 3068kB
Length 1241
Lang C++
Submitted 2019-10-14 21:06:57
RemoteRunId 20959589