首页 > 代码库 > bzoj2396 神奇的矩阵
bzoj2396 神奇的矩阵
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2396
【题解】
我们随机一个1*n的矩阵D,根据矩阵乘法的结合律,如果A*B=C,右D*(A*B)=D*C,即(D*A)*B=C,那么矩阵乘法就是O(n^2)的复杂度了。
多随机几次即可。
# include <stdio.h> # include <string.h> # include <stdlib.h> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; inline int randi(int n) { return ((rand() << 15) + rand()) % n + 1; } int n; struct mat { int n, m, a[510][510]; inline void init (int _n, int _m) { n = _n, m = _m; memset(a, 0, sizeof a); } }A, B, C, o, tA, tB, tC; mat ta, tb, tc; inline void mul() { tc.init(ta.n, tb.m); for (int i=1; i<=tc.n; ++i) for (int j=1; j<=tc.m; ++j) for (int k=1; k<=ta.m; ++k) tc.a[i][j] = tc.a[i][j] + ta.a[i][k] * tb.a[k][j]; } int main() { while(~scanf("%d", &n)) { A.init(n, n); B.init(n, n); C.init(n, n); for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) scanf("%d", &A.a[i][j]); for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) scanf("%d", &B.a[i][j]); for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) scanf("%d", &C.a[i][j]); for (int T = 1; T <= 10; ++T) { o.init(1, n); for (int i=1; i<=n; ++i) o.a[1][i] = randi(n); ta = o, tb = C; mul(); tC = tc; ta = o, tb = A; mul(); tA = tc; ta = tA, tb = B; mul(); tB = tc; for (int i=1; i<=n; ++i) if(tC.a[1][i] != tB.a[1][i]) { puts("No"); goto END; } } puts("Yes"); END:; } return 0; }
bzoj2396 神奇的矩阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。