BZOJ2396 神奇的矩阵 <随机化>

Problem

神奇的矩阵

Time Limit: $5 Sec$
Memory Limit: $512 MB$

Description

给出三个行数和列数均为$N$的矩阵$A$、$B$、$C$，判断$A\times B=C$是否成立。

Input

题目可能包含若干组数据。
对于每组数据，第一行一个数$N$，接下来给出三个$N\times N$的矩阵，依次为$A$、$B$、$C$三个矩阵。

Output

对于每组数据，若$A\times B=C$成立，则输出$Yes$，否则$No$。每个答案占一行。

Sample Input

1
2
2
100

Sample Output

No

HINT

对于$90\%$的数据，$N$不超过$100$；
对于$100\%$的数据，$N$不超过$1000$，矩阵中的数字大于等于$0$小于$1000$，数据组数不超过$5$组。

标签：矩阵乘法 随机化

Solution

挺巧妙的一道随机化题。
首先考虑直接乘，由于$N\le 1000$，而矩乘是$O(n^3)$，肯定会$TLE$。
我们发现矩阵太大了，那么我们就要压缩矩阵，把这样一个正方形的矩阵压缩为一个行矩阵或列矩阵。
我们先随机出一个$1\times n$的列矩阵$R$，这样$A\times B\times R=A\times (B\times R)$，将结果与$C\times R$比较。这样乘法的复杂度就降为$O(n^2)$，比较复杂度为$O(n)$，总复杂度为$O(n^2)$。如果觉得随机一次不保险，还可以多随机几次，不过只随一次也很容易过。

Code

#include <bits/stdc++.h>
#define MAX_N 1000
#define MOD 1000000007
using namespace std;
int n;
struct Matrix {
    int r, c;	long long ele[MAX_N][MAX_N];
    inline Matrix operator * (const Matrix &x) const {
        Matrix ret;	memset(ret.ele, 0, sizeof(ret.ele));
        for (int i = 0; i < (ret.r = r); i++)
            for (int j = 0; j < (ret.c = x.c); j++)
                for (int k = 0; k < c; k++)
                    ret.ele[i][j] = (ret.ele[i][j]+ele[i][k]*x.ele[k][j])%MOD;
        return ret;
    }
} A, B, C, R;
int main() {
    while (scanf("%d", &n)) {
        A.r = A.c = n;	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%lld", &A.ele[i][j]);
        B.r = B.c = n;	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%lld", &B.ele[i][j]);
        C.r = C.c = n;	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%lld", &C.ele[i][j]);
        srand(19260817);	R.r = n, R.c = 1;	for (int i = 0; i < n; i++) R.ele[i][0] = rand()*rand()%MOD;
        A = A*(B*R), C = C*R;	bool flag = true;	for (int i = 0; i < n; i++) flag &= (A.ele[i][0] == C.ele[i][0]);
        puts(flag ? "Yes" : "No");
    }
    return 0;
}