Problem

codeforces.com/gym/101341/problem/I

vjudge.net/contest/162325#problem/I

Meaning

给 3 个 n * n 的矩阵 A，B，C，问是否 A x B = C

Analysis

暴力检验 TLE，要用随机算法。

由：

A x B = C

得：

A x B x D = C x D（其中D 的行数也为 n，列数随意。为了省时间，将D 设计为 n * 1 的列向量）

由矩阵结合率，有：

A x ( B x D ) = C x D

记 B x D = E，C x D =F，则有：

A x E = F

记 A x E = G，则：

G = F

如果验证到 G != F，则说明一定有 A x B != C；但如果 G = F，未必有 A x B = C，所以要多验证几次，如果在规定次数的检验内都查不到错，就当它A x B = C 了（如果这都不对也没办法了…）。

感觉有点像字符串的 Hash（映射），总有一定概率有 Hash 值冲突，但概率小到一定范围内就认为是不同的，因为这时出错概率很小，可以视为不可能事件。

Code

#include <cmath> #include <cstdio> #include <cstdlib> #include <ctime> using namespace std; const int N = 1000, MOD = 1e9 + 7; int a[N][N], b[N][N], c[N][N]; int d[N], e[N], f[N]; void mat_mul(int x[][N], int y[], int z[], int n) { long long tmp; for(int row = 0; row < n; ++row) { tmp = 0; for(int col = 0; col < n; ++col) tmp = (tmp + (long long)x[row][col] * y[col]) % MOD; z[row] = tmp; } } int main() { srand((unsigned)time(NULL)); int n; scanf("%d", &n); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d", a[i]+j); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d", b[i]+j); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d", c[i]+j); bool same = true; for(int t = 10; same && --t; ) { for(int i = 0; i < n; ++i) d[i] = e[i] = rand(); mat_mul(b, d, f, n); // BxD 中间结果放进 F mat_mul(a, f, d, n); // AxF 最终结果放回 D mat_mul(c, e, f, n); // CxE 结果放进 F for(int i = 0; i < n; ++i) if(d[i] != f[i]) { same = false; break; } } puts(same ? "YES" : "NO"); return 0; }