fork(7) download
  1. public class Matrix {
  2.  
  3.  
  4. static int N; // size of the matrix
  5.  
  6. /**
  7. * compute pow(base, pow)
  8. * O(N^3) * logN
  9. **/
  10. static long[][] matrixPower(long [][] base, long pow) {
  11. long [][] ans = new long [N][N];
  12. // generate identity matrix
  13. for (int i = 0; i < N; i++) ans[i][i] = 1;
  14.  
  15. // binary exponentiation
  16. while ( pow != 0 ) {
  17. if ( (pow&1) != 0 ) ans = multiplyMatrix(ans, base);
  18.  
  19. base = multiplyMatrix(base, base);
  20.  
  21. pow >>= 1;
  22. }
  23.  
  24. return ans;
  25. }
  26.  
  27. /**
  28. * compute m * m2
  29. * O(N^3)
  30. **/
  31. static long [][] multiplyMatrix(long [][] m, long [][] m2) {
  32. long [][] ans = new long [N][N];
  33.  
  34. for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
  35. ans[i][j] = 0;
  36. for (int k = 0; k < N; k++) {
  37. ans[i][j] += m[i][k] * m2[k][j];
  38. }
  39. }
  40.  
  41. return ans;
  42. }
  43.  
  44. }
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
Main.java:1: error: class Matrix is public, should be declared in a file named Matrix.java
public class Matrix {
       ^
1 error
stdout
Standard output is empty