fork download
copy 
  1. import java.io.FileInputStream;
  2. import java.util.Arrays;
  3. import java.io.BufferedWriter;
  4. import java.util.InputMismatchException;
  5. import java.util.ArrayList;
  6. import java.io.InputStream;
  7. import java.util.List;
  8. import java.io.OutputStreamWriter;
  9. import java.math.BigInteger;
  10. import java.io.OutputStream;
  11. import java.io.PrintStream;
  12. import java.io.PrintWriter;
  13. import java.io.Writer;
  14. import java.io.IOException;
  15. import java.io.FileOutputStream;
  16.  
  17. /**
  18.  * Built using CHelper plug-in
  19.  * Actual solution is at the top
  20.  * @author ilyakor
  21.  */
  22. public class Main {
  23. 	public static void main(String[] args) {
  24. 		InputStream inputStream;
  25. 		try {
  26. 			inputStream = new FileInputStream("higher.in");
  27. 		} catch (IOException e) {
  28. 			throw new RuntimeException(e);
  29. 		}
  30. 		OutputStream outputStream;
  31. 		try {
  32. 			outputStream = new FileOutputStream("higher.out");
  33. 		} catch (IOException e) {
  34. 			throw new RuntimeException(e);
  35. 		}
  36. 		InputReader in = new InputReader(inputStream);
  37. 		OutputWriter out = new OutputWriter(outputStream);
  38. 		TaskH solver = new TaskH();
  39. 		try {
  40. 			int testNumber = 1;
  41. 			while (true)
  42. 				solver.solve(testNumber++, in, out);
  43. 		} catch (UnknownError e) {
  44. 			out.close();
  45. 		}
  46. 	}
  47. }
  48.  
  49. class TaskH {
  50.     OutputWriter out;
  51.  
  52.     BigInteger[][] a;
  53.     BigInteger[][] l, lRev, r, rRev;
  54.  
  55.     public void solve(int testNumber, InputReader in, OutputWriter out) {
  56.         this.out = out;
  57.         int n = in.nextInt();
  58.         if (n == 0) throw new UnknownError();
  59.  
  60.         a = new BigInteger[n][n];
  61.         BigInteger[][] aOld = new BigInteger[n][n];
  62.         for (int i = 0; i < n; ++i)
  63.             for (int j = 0; j < n; ++j) {
  64.                 a[i][j] = BigInteger.valueOf(in.nextInt());
  65.                 aOld[i][j] = a[i][j];
  66.             }
  67.         l = diag(n);
  68.         lRev = diag(n);
  69.         r = diag(n);
  70.         rRev = diag(n);
  71.  
  72.         for (int i = 0; i < n; ++i) {
  73.             subMatrixGcd(i);
  74.             if (a[i][i].equals(BigInteger.ZERO)) continue;
  75.             for (int j = i + 1; j < n; ++j) {
  76.                 //Assert.assertTrue(a[j][i].mod(a[i][i]).equals(BigInteger.ZERO));
  77.                 BigInteger div = div(a[j][i], a[i][i]);
  78.                 subtractRow(j, i, div);
  79.             }
  80.             for (int j = i + 1; j < n; ++j) {
  81.                 //Assert.assertTrue(a[i][j].mod(a[i][i]).equals(BigInteger.ZERO));
  82.                 BigInteger div = div(a[i][j], a[i][i]);
  83.                 subtractCol(j, i, div);
  84.             }
  85.         }
  86.  
  87.         printMatr(l);
  88.         lRev = inverse(l);
  89.         printMatr(lRev);
  90.         printMatr(r);
  91.         rRev = inverse(r);
  92.         printMatr(rRev);
  93.  
  94.  
  95.         BigInteger[][] diag = multiply(l, lRev);
  96.         assertUni(diag);
  97.         diag = multiply(r, rRev);
  98.         assertUni(diag);
  99.  
  100.         diag = multiply(multiply(l, aOld), r);
  101.         assertDiag(diag);
  102.     }
  103.  
  104.     private void assertUni(BigInteger[][] a) {
  105.         for (int i = 0; i < a.length; ++i)
  106.             for (int j = 0; j < a[i].length; ++j) {
  107.                 if (i == j) Assert.assertTrue(a[i][j].equals(BigInteger.ONE));
  108.                 else  Assert.assertTrue(a[i][j].equals(BigInteger.ZERO));
  109.             }
  110.     }
  111.  
  112.     private void assertDiag(BigInteger[][] a) {
  113.         for (int i = 0; i < a.length; ++i)
  114.             for (int j = 0; j < a[i].length; ++j) {
  115.                 if (i == j) {
  116.                     if (i > 0 && a[i][i].compareTo(BigInteger.ZERO) != 0)
  117.                         Assert.assertTrue(a[i][i].abs().mod(a[i - 1][i - 1].abs()).equals(BigInteger.ZERO));
  118.                 }  else  Assert.assertTrue(a[i][j].equals(BigInteger.ZERO));
  119.             }
  120.     }
  121.  
  122.     private void subtractRow(int target, int source, BigInteger coef) {
  123.         for (int i = 0; i < a[target].length; ++i) {
  124.             a[target][i] = a[target][i].subtract(a[source][i].multiply(coef));
  125.             l[target][i] = l[target][i].subtract(l[source][i].multiply(coef));
  126.         }
  127.     }
  128.  
  129.     private void multRow(int target, int coef) {
  130.         for (int i = 0; i < a[target].length; ++i) {
  131.             a[target][i] = a[target][i].multiply(BigInteger.valueOf(coef));
  132.             l[target][i] = l[target][i].multiply(BigInteger.valueOf(coef));
  133.         }
  134.     }
  135.  
  136.     private void subtractCol(int target, int source, BigInteger coef) {
  137.         for (int i = 0; i < a.length; ++i) {
  138.             a[i][target] = a[i][target].subtract(a[i][source].multiply(coef));
  139.             r[i][target] = r[i][target].subtract(r[i][source].multiply(coef));
  140.         }
  141.     }
  142.  
  143.     private void multCol(int target, int coef) {
  144.         for (int i = 0; i < a.length; ++i) {
  145.             a[i][target] = a[i][target].multiply(BigInteger.valueOf(coef));
  146.             r[i][target] = r[i][target].multiply(BigInteger.valueOf(coef));
  147.         }
  148.     }
  149.  
  150.  
  151.     void swapRows(int x, int y) {
  152.         BigInteger[] tmp = a[x];
  153.         a[x] = a[y];
  154.         a[y] = tmp;
  155.  
  156.         tmp = l[x];
  157.         l[x] = l[y];
  158.         l[y] = tmp;
  159.     }
  160.  
  161.     void swapCols(int x, int y) {
  162.         for (int i = 0; i < a.length; ++i) {
  163.             BigInteger tmp = a[i][x];
  164.             a[i][x] = a[i][y];
  165.             a[i][y] = tmp;
  166.  
  167.             tmp = r[i][x];
  168.             r[i][x] = r[i][y];
  169.             r[i][y] = tmp;
  170.         }
  171.     }
  172.  
  173.     private void subMatrixGcd(int from) {
  174.         int n = a.length;
  175.         for (int col = n - 1; col >= from; --col) {
  176.             if (col + 1 < n) {
  177.                 GcdRow(from, col, col + 1);
  178.             }
  179.             for (int row = from + 1; row < n; ++row) {
  180.                 GcdCol(col, from, row);
  181.             }
  182.         }
  183.     }
  184.  
  185.     void GcdCol(int col, int row1, int row2) {
  186.         if (a[row1][col].compareTo(BigInteger.ZERO) < 0) {
  187.             multRow(row1, -1);
  188.         }
  189.         if (a[row2][col].compareTo(BigInteger.ZERO) < 0) {
  190.             multRow(row2, -1);
  191.         }
  192.         while (a[row2][col].compareTo(BigInteger.ZERO) != 0) {
  193.             BigInteger div = div(a[row1][col], a[row2][col]);
  194.             subtractRow(row1, row2, div);
  195.             swapRows(row1, row2);
  196.         }
  197.     }
  198.  
  199.     void GcdRow(int row, int col1, int col2) {
  200.         if (a[row][col1].compareTo(BigInteger.ZERO) < 0) {
  201.             multCol(col1, -1);
  202.         }
  203.         if (a[row][col2].compareTo(BigInteger.ZERO) < 0) {
  204.             multCol(col2, -1);
  205.         }
  206.         while (a[row][col2].compareTo(BigInteger.ZERO) != 0) {
  207.             BigInteger div = div(a[row][col1], a[row][col2]);
  208.             subtractCol(col1, col2, div);
  209.             swapCols(col1, col2);
  210.         }
  211.     }
  212.  
  213.  
  214.     private void printMatr(BigInteger[][] a) {
  215.         for (int i = 0; i < a.length; ++i) {
  216.             for (BigInteger x : a[i])
  217.                 out.print(x + " ");
  218.             out.printLine();
  219.         }
  220.         out.printLine();
  221.     }
  222.  
  223.     private BigInteger[][] diag(int n) {
  224.         BigInteger[][] res = new BigInteger[n][n];
  225.         for (int i = 0; i < n; ++i)
  226.             for (int j = 0; j < n; ++j)
  227.                 res[i][j] = i == j ? BigInteger.ONE: BigInteger.ZERO;
  228.         return res;
  229.     }
  230.  
  231.     private BigInteger[][] inverse(BigInteger[][] a) {
  232.         int n = a.length;
  233.         BigInteger[][] res = new BigInteger[n][n];
  234.         BigInteger det = calcDet(a);
  235.         for (int x = 0; x < n; ++x) {
  236.             for (int y = 0; y < n; ++y) {
  237.                 BigInteger[][] minor = new BigInteger[n - 1][n - 1];
  238.                 for (int i = 0, row = 0; i < n; ++i) {
  239.                     if (i == y) continue;
  240.                     for (int j = 0, col = 0; j < n; ++j) {
  241.                         if (j == x) continue;
  242.                         minor[row][col] = a[i][j];
  243.                         ++col;
  244.                     }
  245.                     ++row;
  246.                 }
  247.                 BigInteger val = calcDet(minor);
  248.                 res[x][y] = div(val, det);
  249.                 if ((x + y) % 2 == 1)
  250.                     res[x][y] = res[x][y].negate();
  251.             }
  252.         }
  253.         return res;
  254.     }
  255.  
  256.     private BigInteger calcDet(BigInteger[][] a) {
  257.         int n = a.length;
  258.         int[] p = new int[n];
  259.         for (int i = 0; i < n; ++i) {
  260.             p[i] = i;
  261.         }
  262.         BigInteger res = BigInteger.ZERO;
  263.         do {
  264.             int s = 1;
  265.             for (int i = 0; i < n; ++i)
  266.                 for (int j = i + 1; j < n; ++j)
  267.                     if (p[i] > p[j]) s = -s;
  268.             BigInteger val = BigInteger.valueOf(s);
  269.             for (int i = 0; i < n; ++i)
  270.                 val = val.multiply(a[i][p[i]]);
  271.             res = res.add(val);
  272.         } while (Permutations.nextPermutation(p));
  273.         return res;
  274.     }
  275.  
  276.     BigInteger[][] multiply(BigInteger[][] a, BigInteger[][] b) {
  277.         int n = a.length;
  278.         BigInteger[][] res = new BigInteger[n][n];
  279.         for (int i = 0; i < n; ++i)
  280.             for (int j = 0; j < n; ++j)
  281.                 res[i][j] = BigInteger.ZERO;
  282.         for (int i = 0; i < n; ++i)
  283.             for (int j = 0; j < n; ++j)
  284.                 for (int k = 0; k < n; ++k)
  285.                     res[i][j] = res[i][j].add(a[i][k].multiply(b[k][j]));
  286.         return res;
  287.     }
  288.  
  289.     BigInteger div(BigInteger a, BigInteger b) {
  290.         BigInteger res = a.abs().divide(b.abs());
  291.         if (b.compareTo(BigInteger.ZERO) < 0)
  292.             res = res.negate();
  293.         if (a.compareTo(BigInteger.ZERO) < 0)
  294.             res = res.negate();
  295.         return res;
  296.     }
  297. }
  298.  
  299. class OutputWriter {
  300.     private final PrintWriter writer;
  301.  
  302.     public OutputWriter(OutputStream outputStream) {
  303.         writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  304.     }
  305.  
  306.     public void print(Object... objects) {
  307.         for (int i = 0; i < objects.length; i++) {
  308.             if (i != 0) {
  309.                 writer.print(' ');
  310.             }
  311.             writer.print(objects[i]);
  312.         }
  313.     }
  314.  
  315.     public void printLine(Object... objects) {
  316.         print(objects);
  317.         writer.println();
  318.     }
  319.  
  320.     public void close() {
  321.         writer.close();
  322.     }
  323.  
  324. }
  325.  
  326. class InputReader {
  327.     private InputStream stream;
  328.     private byte[] buffer = new byte[10000];
  329.     private int cur;
  330.     private int count;
  331.  
  332.     public InputReader(InputStream stream) {
  333.         this.stream = stream;
  334.     }
  335.  
  336.     public static boolean isSpace(int c) {
  337.         return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  338.     }
  339.  
  340.     public int read() {
  341.         if (count == -1) {
  342.             throw new InputMismatchException();
  343.         }
  344.         try {
  345.             if (cur >= count) {
  346.                 cur = 0;
  347.                 count = stream.read(buffer);
  348.                 if (count <= 0)
  349.                     return -1;
  350.             }
  351.         } catch (IOException e) {
  352.             throw new InputMismatchException();
  353.         }
  354.         return buffer[cur++];
  355.     }
  356.  
  357.     public int readSkipSpace() {
  358.         int c;
  359.         do {
  360.             c = read();
  361.         } while (isSpace(c));
  362.         return c;
  363.     }
  364.  
  365.     public int nextInt() {
  366.         int sgn = 1;
  367.         int c = readSkipSpace();
  368.         if (c == '-') {
  369.             sgn = -1;
  370.             c = read();
  371.         }
  372.         int res = 0;
  373.         do {
  374.             if (c < '0' || c > '9') {
  375.                 throw new InputMismatchException();
  376.             }
  377.             res = res * 10 + c - '0';
  378.             c = read();
  379.         } while (!isSpace(c));
  380.         res *= sgn;
  381.         return res;
  382.     }
  383.  
  384. }
  385.  
  386. class Assert {
  387.  
  388.     public static void assertTrue(boolean flag) {
  389.         if (!flag)
  390.         while (true);
  391. //        if (!flag)
  392. //            throw new AssertionError();
  393.     }
  394.  
  395. }
  396.  
  397. class Permutations {
  398.  
  399.     public static boolean nextPermutation(int[] p) {
  400. 		for (int a = p.length - 2; a >= 0; --a)
  401. 			if (p[a] < p[a + 1])
  402. 				for (int b = p.length - 1;; --b)
  403. 					if (p[b] > p[a]) {
  404. 						int t = p[a];
  405. 						p[a] = p[b];
  406. 						p[b] = t;
  407. 						for (++a, b = p.length - 1; a < b; ++a, --b) {
  408. 							t = p[a];
  409. 							p[a] = p[b];
  410. 							p[b] = t;
  411. 						}
  412. 						return true;
  413. 					}
  414. 		return false;
  415. 	}
  416.  
  417. }
  418.  
Runtime error #stdin #stdout #stderr 0.09s 320320KB
comments (?)
stdin
copy 
3
1 2 3
6 5 4
7 8 9
0
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.RuntimeException: java.io.FileNotFoundException: higher.in (No such file or directory)
	at Main.main(Main.java:28)
Caused by: java.io.FileNotFoundException: higher.in (No such file or directory)
	at java.io.FileInputStream.open(Native Method)
	at java.io.FileInputStream.<init>(FileInputStream.java:138)
	at java.io.FileInputStream.<init>(FileInputStream.java:93)
	at Main.main(Main.java:26)
https://ideone.com/KzB2UD
language:
Java (HotSpot 12)
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!