BZOJ2396 神奇的矩阵 <随机化>

Problem

神奇的矩阵

Time Limit:
Memory Limit:

Description

给出三个行数和列数均为的矩阵、、，判断是否成立。

Input

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

Output

对于每组数据，若成立，则输出，否则。每个答案占一行。

Sample Input

1
2
2
100

Sample Output

No

HINT

对于的数据，不超过；
对于的数据，不超过，矩阵中的数字大于等于小于，数据组数不超过组。

标签：矩阵乘法 随机化

Solution

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

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;
}