首页 > 代码库 > Codeforces Gym101341I：Matrix God（随机化构造矩阵降维）***
Codeforces Gym101341I：Matrix God（随机化构造矩阵降维）***
http://codeforces.com/gym/101341/problem/I
题意：给三个N*N的矩阵，问a*b是否等于c。
思路：之前遇到过差不多的题目，当时是随机行（点），然后验证，不满足就退出。还有暴力弄的（当时的数据是500）。也提到过这样的解法，当时没用这种做法做一遍。
就是构造多一个矩阵d。
由于矩阵乘法满足结合律：a * (b * d) = c * d. d是一个n*1的矩阵，b * d之后会得到一个n * 1的矩阵，因此只需要O（n^2）就可以验证是否正确。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 #define N 1010 5 const int MOD = 1e9 + 7; 6 LL a[N][N], b[N][N], c[N][N]; 7 LL d[N], t0[N], t1[N], t2[N]; int n; 8 9 int main() {10 scanf("%d", &n);11 srand(time(NULL));12 for(int i = 1; i <= n; i++)13 for(int j = 1; j <= n; j++) scanf("%lld", &a[i][j]);14 for(int i = 1; i <= n; i++)15 for(int j = 1; j <= n; j++) scanf("%lld", &b[i][j]);16 for(int i = 1; i <= n; i++)17 for(int j = 1; j <= n; j++) scanf("%lld", &c[i][j]);18 bool flag = 1;19 for(int cas = 1; cas <= 5 && flag; cas++) {20 for(int i = 1; i <= n; i++) d[i] = rand() % MOD;21 for(int i = 1; i <= n; i++) {22 t2[i] = 0;23 for(int j = 1; j <= n; j++)24 t2[i] = (t2[i] + c[i][j] * d[j]) % MOD;25 }26 27 for(int i = 1; i <= n; i++) {28 t1[i] = 0;29 for(int j = 1; j <= n; j++)30 t1[i] = (t1[i] + b[i][j] * d[j]) % MOD;31 }32 33 for(int i = 1; i <= n && flag; i++) {34 t0[i] = 0;35 for(int j = 1; j <= n; j++)36 t0[i] = (t0[i] + a[i][j] * t1[j]) % MOD;37 if(t0[i] != t2[i]) flag = 0;38 }39 }40 if(flag) puts("YES");41 else puts("NO");42 return 0;43 }
Codeforces Gym101341I：Matrix God（随机化构造矩阵降维）***
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。