fork download
  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 res = a.abs().divide(b.abs());
  290. if (b.compareTo(BigInteger.ZERO) < 0)
  291. res = res.negate();
  292. if (a.compareTo(BigInteger.ZERO) < 0)
  293. res = res.negate();
  294. return res;
  295. }
  296. }
  297.  
  298. class OutputWriter {
  299. private final PrintWriter writer;
  300.  
  301. public OutputWriter(OutputStream outputStream) {
  302. writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  303. }
  304.  
  305. public void print(Object... objects) {
  306. for (int i = 0; i < objects.length; i++) {
  307. if (i != 0) {
  308. writer.print(' ');
  309. }
  310. writer.print(objects[i]);
  311. }
  312. }
  313.  
  314. public void printLine(Object... objects) {
  315. print(objects);
  316. writer.println();
  317. }
  318.  
  319. public void close() {
  320. writer.close();
  321. }
  322.  
  323. }
  324.  
  325. class InputReader {
  326. private InputStream stream;
  327. private byte[] buffer = new byte[10000];
  328. private int cur;
  329. private int count;
  330.  
  331. public InputReader(InputStream stream) {
  332. this.stream = stream;
  333. }
  334.  
  335. public static boolean isSpace(int c) {
  336. return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  337. }
  338.  
  339. public int read() {
  340. if (count == -1) {
  341. throw new InputMismatchException();
  342. }
  343. try {
  344. if (cur >= count) {
  345. cur = 0;
  346. count = stream.read(buffer);
  347. if (count <= 0)
  348. return -1;
  349. }
  350. } catch (IOException e) {
  351. throw new InputMismatchException();
  352. }
  353. return buffer[cur++];
  354. }
  355.  
  356. public int readSkipSpace() {
  357. int c;
  358. do {
  359. c = read();
  360. } while (isSpace(c));
  361. return c;
  362. }
  363.  
  364. public int nextInt() {
  365. int sgn = 1;
  366. int c = readSkipSpace();
  367. if (c == '-') {
  368. sgn = -1;
  369. c = read();
  370. }
  371. int res = 0;
  372. do {
  373. if (c < '0' || c > '9') {
  374. throw new InputMismatchException();
  375. }
  376. res = res * 10 + c - '0';
  377. c = read();
  378. } while (!isSpace(c));
  379. res *= sgn;
  380. return res;
  381. }
  382.  
  383. }
  384.  
  385. class Assert {
  386.  
  387. public static void assertTrue(boolean flag) {
  388. if (!flag)
  389. while (true);
  390. // if (!flag)
  391. // throw new AssertionError();
  392. }
  393.  
  394. }
  395.  
  396. class Permutations {
  397.  
  398. public static boolean nextPermutation(int[] p) {
  399. for (int a = p.length - 2; a >= 0; --a)
  400. if (p[a] < p[a + 1])
  401. for (int b = p.length - 1;; --b)
  402. if (p[b] > p[a]) {
  403. int t = p[a];
  404. p[a] = p[b];
  405. p[b] = t;
  406. for (++a, b = p.length - 1; a < b; ++a, --b) {
  407. t = p[a];
  408. p[a] = p[b];
  409. p[b] = t;
  410. }
  411. return true;
  412. }
  413. return false;
  414. }
  415.  
  416. }
  417.  
Runtime error #stdin #stdout #stderr 0.09s 320320KB
stdin
3
1 2 3
6 5 4
7 8 9
0
stdout
Standard output is empty
stderr
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)