首页 > 代码库 > BZOJ2396 神奇的矩阵
BZOJ2396 神奇的矩阵
题意:有三个N*N的矩阵a,b,c,判断a*b是否等于c.
思路:暴力判断O(N*3),我没试能不能过。
正解是随机化算法,随机构造列向量p,然后分别计算a*(b*p)和c*p,比较之。
这个过程仅为O(N^2).
随机多组即可。
Code:
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <climits> #include <cstdlib> using namespace std; #define N 1010 struct Matrix { int w, h, v[N][N]; Matrix() { memset(v, 0, sizeof v); } bool operator == (const Matrix &B) const { if (w != B.w || h != B.h) return 0; register int i, j; for(i = 0; i < w; ++i) for(j = 0; j < h; ++j) if (v[i][j] != B.v[i][j]) return 0; return 1; } void operator = (const Matrix &B) { w = B.w, h = B.h; for(int i = 0; i < w; ++i) for(int j = 0; j < h; ++j) v[i][j] = B.v[i][j]; } void operator *= (const Matrix &B); }A, B, C, ran, tmp1, tmp2, get; void Matrix::operator *= (const Matrix &B) { memset(get.v, 0, sizeof get.v); get.w = w, get.h = B.h; register int i, j, k; for(i = 0; i < get.w; ++i) for(k = 0; k < h; ++k) for(j = 0; j < get.h; ++j) get.v[i][j] += v[i][k] * B.v[k][j]; *this = get; } int main() { int n; register int i, j; while(scanf("%d", &n) != EOF) { A.w = A.h = n; B.w = B.h = n; C.w = C.h = n; for(i = 0; i < n; ++i) for(j = 0; j < n; ++j) scanf("%d", &A.v[i][j]); for(i = 0; i < n; ++i) for(j = 0; j < n; ++j) scanf("%d", &B.v[i][j]); for(i = 0; i < n; ++i) for(j = 0; j < n; ++j) scanf("%d", &C.v[i][j]); int wrong = 0; for(int Case = 1; Case <= 1; ++Case) { ran.w = 1, ran.h = n; for(i = 0; i < n; ++i) ran.v[0][i] = rand(); tmp1 = ran; tmp2 = ran; tmp1 *= A, tmp1 *= B; tmp2 *= C; if (!(tmp1 == tmp2)) { wrong = 1; break; } } if (wrong) puts("No"); else puts("Yes"); } return 0; }
BZOJ2396 神奇的矩阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。