fork(1) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct matrix {
  5.     int mat[31][31];
  6. };
  7.  
  8. long n, m;
  9. matrix E; //единичная матрица
  10.  
  11. matrix mul(matrix A, matrix B) {
  12.     matrix C;
  13.     for(int i = 0; i < n; i++)
  14.         for(int j = 0; j < n; j++) {
  15.             C.mat[i][j] = 0;
  16.             for(int k = 0; k < n; k++)
  17.                 C.mat[i][j] += A.mat[i][k] * B.mat[k][j] % m;
  18.         }
  19. 	return C;
  20. }
  21.  
  22. matrix sum(matrix A, matrix B) { 
  23.     for(int i = 0; i < n; i++)
  24.         for(int j = 0; j < n; j++)
  25.             A.mat[i][j] += B.mat[i][j] % m;
  26.     return A;
  27. }
  28.  
  29. matrix power(matrix A, int k) { 
  30.     if (k == 1)
  31.     	return A;
  32.     matrix B = power(A, k / 2);
  33.     B = mul(B, B);
  34.     if (k % 2 != 0)
  35.     	B = mul(B, A);
  36.     return B;
  37. }
  38.  
  39. matrix res(matrix A, int k) {
  40.     if (k == 1)
  41.     	return A;
  42.     if (k % 2 == 0) {
  43.         matrix B = res(A, k / 2);
  44.         return mul(sum(power(A, k / 2), E), B);
  45.     }
  46.     else {
  47.         matrix B = res(A, k / 2);
  48.         matrix C = power(A, (k+1) / 2);
  49.         return sum(C, mul(B, sum(C, E)));
  50.     }
  51. }
  52.  
  53. int main() {
  54.     long long k;
  55.     matrix A;
  56. 	cin >> n >> k >> m;
  57.     for(int i = 0; i < n; i++) {
  58.         E.mat[i][i] = 1;
  59.         for(int j = 0; j < n; j++) 
  60.             cin >> A.mat[i][j];
  61.     }
  62.     matrix ans = res(A, k);
  63.     for(int i = 0; i < n; i++) {
  64.         for(int j = 0; j < n; j++) {
  65.            if (j != 0)
  66.             	cout << " ";
  67.             cout << ans.mat[i][j] % m;
  68.         }
  69.         cout << "\n";
  70.     }
  71.     return 0;
  72. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
2 2 4
0 1 
1 1
stdout
copy 
1 2
2 3
https://ideone.com/5HPBQs
Matrix Power Series
language:
C++ (gcc 8.3)
created:
5 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!