fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. bool valid(const vector<vector<int>>& a, const vector<vector<int>>& b, const vector<vector<int>>& c, int n) {
  6.     vector<int> p(n);
  7.     for (int i = 0; i < n; ++i) p[i] = rand() % 2;
  8.  
  9.     vector<int> br(n, 0), cr(n, 0), ar(n, 0);
  10.  
  11.     for (int i = 0; i < n; ++i)
  12.         for (int j = 0; j < n; ++j) {
  13.             br[i] = (br[i] + b[i][j] * p[j]) % 10;
  14.             cr[i] = (cr[i] + c[i][j] * p[j]) % 10;
  15.         }
  16.     for(int i = 0; i < n; ++i)
  17.         for (int j = 0; j < n; ++j)
  18.             ar[i] = (ar[i] + a[i][j] * br[j]) % 10;
  19.     for(int i = 0; i < n; ++i){
  20.         if (ar[i] != cr[i])
  21.             return false;
  22.         }
  23.     return true;
  24. }
  25.  
  26. bool freivald(const vector<vector<int>>& a, const vector<vector<int>>& b, const vector<vector<int>>& c, int n, int k = 30) {
  27.     for (int i = 0; i < k; ++i)
  28.         if (!valid(a, b, c, n)) return false;
  29.     return true;
  30. }
  31. signed main() {
  32.     ios::sync_with_stdio(false);
  33.     cin.tie(nullptr);
  34.     int t;
  35.     cin >> t;
  36.     while (t--) {
  37.         int n;
  38.         cin >> n;
  39.         vector<vector<int>> a(n, vector<int>(n));
  40.         vector<vector<int>> b(n, vector<int>(n));
  41.         vector<vector<int>> c(n, vector<int>(n));
  42.         for (int i = 0; i < n; ++i) {
  43.             string s;
  44.             cin >> s;
  45.             for (int j = 0; j < n; ++j)
  46.                 a[i][j] = s[j] - '0';
  47.         }
  48.  
  49.         for (int i = 0; i < n; ++i) {
  50.             string s;
  51.             cin >> s;
  52.             for (int j = 0; j < n; ++j)
  53.                 b[i][j] = s[j] - '0';
  54.         }
  55.  
  56.         for (int i = 0; i < n; ++i) {
  57.             string s;
  58.             cin >> s;
  59.             for (int j = 0; j < n; ++j)
  60.                 c[i][j] = s[j] - '0';
  61.         }
  62.  
  63.         if (freivald(a, b, c, n))
  64.             cout << "YES\n";
  65.         else
  66.             cout << "NO\n";
  67.     }
  68. }
  69.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
2
2
12
34
43
21
85
03
2
12
34
43
21
85
00
stdout
copy 
YES
NO
https://ideone.com/4bertd
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!