fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cassert>
  4. #include <iostream>
  5. #include <set>
  6. #include <vector>
  7. #include <cstring>
  8. #include <string>
  9. #include <algorithm>
  10. #include <numeric>
  11. #include <cmath>
  12. #include <complex>
  13. #include <map>
  14. #include <queue>
  15. using namespace std;
  16. typedef long long ll;
  17. typedef vector<int> vi;
  18. typedef vector<ll> vl;
  19. typedef vector<vi> vvi;
  20. typedef vector<vl> vvl;
  21. typedef vector<double> vd;
  22. typedef pair<int, int> pii;
  23. typedef pair<double, double> pdd;
  24. typedef vector<pii> vii;
  25. typedef vector<string> vs;
  26.  
  27. void out(vl v) {
  28.     for (int i = 0; i < v.size(); ++i)
  29.         cout << v[i] << ' ';
  30.     cout << endl;
  31. }
  32.  
  33. void out(vvl v) {
  34.     for (int i = 0; i < v.size(); ++i)
  35.         out(v[i]);
  36.     cout << endl;
  37. }
  38.  
  39. void outerr(vl v) {
  40.     for (int i = 0; i < v.size(); ++i)
  41.         cerr << v[i] << ' ';
  42.     cerr << endl;
  43. }
  44.  
  45. void outerr(vvl v) {
  46.     for (int i = 0; i < v.size(); ++i)
  47.         outerr(v[i]);
  48.     cerr << endl;
  49. }
  50.  
  51. vvl id (int n) {
  52.     vvl v(n, vl(n));
  53.     for (int i =0 ; i < n; ++i) v[i][i] = 1;
  54.     return v;
  55. }
  56.  
  57. void model(vvl & v, vl x, int inv) {
  58.     if (x.size() == 2) {
  59.         if (x[1] == -1) {
  60.             for (int j = 0; j < v.size(); ++j)
  61.                 v[x[0]][j] *= -1;
  62.             return;
  63.         }
  64.         model(v, {x[0], x[1], 1}, 0);
  65.         model(v, {x[1], x[0], -1}, 0);
  66.         model(v, {x[0], x[1], 1}, 0);
  67.         model(v, {x[0], -1}, 0);
  68.         return;
  69.     }
  70.     if (inv) {
  71.         x[2] *= -1;
  72.     }
  73.     for (int j = 0; j < v.size(); ++j)
  74.         v[x[1]][j] += v[x[0]][j]*x[2];
  75. }
  76.  
  77. vvl tr(vvl v) {
  78.     int n = v.size();
  79.     for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) {
  80.         swap(v[i][j], v[j][i]);
  81.     }
  82.     return v;
  83. }
  84.  
  85. vvl mul(vvl x, vvl y) {
  86.     int n = x.size();
  87.     vvl res(n, vl(n));
  88.     for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
  89.         for (int l = 0; l < n; ++l) {
  90.             //if (abs(y[l][j])) assert(abs(x[i][l]) < 4e18/abs(y[l][j]));
  91.             res[i][j] += x[i][l]*y[l][j];
  92.             //assert(abs(res[i][j]) < 4e18);
  93.         }
  94.     }
  95.     return res;
  96. }
  97.  
  98. int main() {
  99.     freopen("higher.in", "r", stdin);
  100.     freopen("higher.out", "w", stdout);
  101.     int n = 4;
  102.     for (int mask = 0; mask < 100000; ++mask) {
  103.         int m = mask;
  104.     }while (cin >> n) {
  105.         if (n == 0) break;
  106.         vvl a(n, vl(n));
  107.         for (int i = 0; i < n; ++i) for (int j =0 ; j < n; ++j) {
  108.             //a[i][j] = m % 4 - 2;
  109.             //m /= 4;
  110.             cin >> a[i][j];
  111.         }
  112.         vvl a0 = a;
  113.         int b = 0;
  114.         vvl row, col;
  115.         while (b < n) {
  116.             //outerr (a);
  117.             //			out (a);
  118.             ll mi=2.1e18;
  119.             int r,c;
  120.             for (int i = b; i < n; ++i) for (int j = b; j < n; ++j) {
  121.                 if (a[i][j] && abs(a[i][j]) < mi) {
  122.                     r=i; c=j;
  123.                     mi = abs(a[i][j]);
  124.                 }
  125.             }
  126.             if (mi > 2e18) break;
  127.             int r1 = -1, c1 = -1;
  128.             ll m1 = mi;
  129.             for (int i = b; i < n; ++i) for (int j = b; j < n; ++j) if (abs(a[i][j])) {
  130.                 for (int i1 = b; i1 < n; ++i1) if (i1 != i && abs(a[i1][j]) % abs(a[i][j])) {
  131.                     if (abs(a[i1][j]) % abs(a[i][j]) < m1) {
  132.                         m1 = abs(a[i1][j]) % abs(a[i][j]);
  133.                         r = i;
  134.                         r1 = i1; 
  135.                         c = c1 = j;
  136.                     }
  137.                 }
  138.                 for (int j1 = b; j1 < n; ++j1) if (j1 != j && abs(a[i][j1]) % abs(a[i][j])) {
  139.                     if (abs(a[i][j1]) % abs(a[i][j]) < m1) {
  140.                         m1 = abs(a[i][j1]) % abs(a[i][j]);
  141.                         r = r1 = i;
  142.                         c = j;
  143.                         c1 = j1;
  144.                     }
  145.                 }
  146.             }
  147.             if (m1 == mi) {
  148.                 for (int i = b; i < n; ++i) for (int j = b; j < n; ++j) if (abs(a[i][j])) {
  149.                     for (int i1 = b; i1 < n; ++i1) for (int j1 = b; j1 < n; ++j1) if (abs(a[i1][j1]) % abs(a[i][j])) {
  150.                         if (abs(a[i1][j1]) % abs(a[i][j]) < m1) {
  151.                             m1 = abs(a[i1][j1]) % abs(a[i][j]);
  152.                             r = i;
  153.                             r1 = i1;
  154.                             c = j;
  155.                             c1 = j1;
  156.                         }
  157.                     }
  158.                 }
  159.             }
  160.             if (r1 == -1) {
  161.                 if (b != r) {
  162.                     row.push_back({b, r});
  163.                     model(a, row.back(), 0);
  164.                     //a[b].swap(a[r]);
  165.                 }
  166.                 if (b != c) {
  167.                     col.push_back({b, c});
  168.                     for (int i = 0; i < n; ++i)
  169.                         swap(a[i][b], a[i][c]);
  170.                 }
  171.                 for (int i = b + 1; i < n; ++i) {
  172.                     row.push_back({b, i, -a[i][b] / a[b][b]});
  173.                     model(a, row.back(), 0);
  174.                     assert(a[i][b] == 0);
  175.                 }
  176.                 for (int i = b + 1; i < n; ++i) {
  177.                     ll x = -a[b][i] / a[b][b];
  178.                     col.push_back({b, i, x});
  179.                     for (int j = 0; j < n; ++j) {
  180.                         a[j][i] += a[j][b]*x;
  181.                     }
  182.                     assert(a[b][i] == 0);
  183.                 }
  184.                 if (a[b][b] < 0) {
  185.                     row.push_back({b, -1});
  186.                     a[b][b] *= -1;
  187.                 }
  188.                 ++b;	
  189.             } else {
  190.                 assert(abs(a[r1][c1]) % abs(a[r][c]) == m1);
  191.                 if (r != r1 && c != c1) {
  192.                     assert(a[r1][c] % abs(a[r][c]) == 0);
  193.                     row.push_back({r, r1, -a[r1][c] / a[r][c] + 1});
  194.                     r = r1;
  195.                     model(a, row.back(), 0);
  196.                 }
  197.                 if (a[r][c] < 0) {
  198.                     row.push_back({r, -1});
  199.                     model(a, row.back(), 0);
  200.                 }
  201.                 if (a[r1][c1] < 0) {
  202.                     row.push_back({r1, -1});
  203.                     model(a, row.back(), 0);
  204.                 }
  205.                 if (r == r1) {
  206.                     ll x = -a[r][c1]/a[r][c]; //??
  207.                     col.push_back({c, c1, x});
  208.                     for (int i = 0; i < n; ++i)
  209.                         a[i][c1] += a[i][c]*x;
  210.                 } else {
  211.                     assert(c == c1);
  212.                     ll x = -a[r1][c]/a[r][c]; //??
  213.                     row.push_back({r, r1, x});
  214.                     for (int i = 0; i < n; ++i)
  215.                         a[r1][i] += a[r][i]*x;
  216.                 }
  217.                 //assert(abs(a[r1][c1]) == m1);
  218.             }
  219.         }
  220.         vvl L = id(n), L1 = id(n), R = id(n), R1 = id(n);
  221.         vvl test = a0;
  222.         for (int i = 0; i < row.size(); ++i) {
  223.             model(L1, row[row.size()-i-1], 1);
  224.             model(L, row[i], 0);
  225.             model(test, row[i], 0);
  226.         }
  227.         assert(test == mul(L, a0));
  228.         for (int i = 0; i < col.size(); ++i) {
  229.             model(R, col[i], 0);
  230.             model(R1, col[col.size()-i-1], 1);
  231.         }
  232.         R = tr(R);
  233.         R1 = tr(R1);
  234.         out(L);
  235.         out(L1);
  236.         out(R);
  237.         out(R1);
  238.         assert(mul(L, L1) == id(n));
  239.         assert(mul(R, R1) == id(n));
  240.         assert(mul(mul(L, a0),R) == a);
  241.         for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (i != j)
  242.             assert(a[i][j] == 0);
  243.         for (int i = 0; i+1 < n; ++i) {
  244.             assert(a[i][i] == 0 || a[i+1][i+1] % a[i][i] == 0);
  245.             assert(a[i][i] || a[i+1][i+1] == 0);
  246.         }
  247.     }
  248.     return 0;
  249. }
  250.  
Success #stdin #stdout 0s 3112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mXgJCV
language:
C++14 (gcc 8.3)
created:
9 years 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!