fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. int N = 52;
  7. ll mod = 1000000007;
  8. vector<vector<ll>> matrix(N, vector<ll> (N, 0));
  9.  
  10.  
  11. void multiply(int dim, vector<vector<ll>> &A, vector<vector<ll>> &B){
  12.     vector<vector<ll>> res(N, vector<ll> (N, 0));
  13.  
  14.     for (size_t i = 0; i < dim; i++){
  15.         for (size_t j = 0; j < dim; j++){
  16.             res[i][j] = 0;
  17.             for (size_t k = 0; k < dim; k++){
  18.                 ll temp = ((A[i][k] * B[k][j]) % mod);
  19.                 res[i][j] = (res[i][j] + temp)%mod;                
  20.             }            
  21.         }    
  22.     }
  23.  
  24.     for (size_t i = 0; i < dim; i++){
  25.         for (size_t j = 0; j < dim; j++){
  26.             A[i][j] = res[i][j];
  27.         }         
  28.     }
  29. }
  30.  
  31. void power(int m, ll n){    
  32.     vector<vector<ll>> I(N, vector<ll> (N, 0));
  33.  
  34.     for (size_t i = 0; i < m; i++){
  35.         for (size_t j = 0; j < m; j++){
  36.             I[i][j] = (i == j ? 1 : 0);
  37.         }    
  38.     }
  39.  
  40.     while(n){
  41.         if (n&1){
  42.             multiply(m, I, matrix);
  43.             n -= 1;
  44.         }
  45.         else{
  46.             multiply(m, matrix, matrix);
  47.             n /= 2;
  48.         }                   
  49.     }
  50.  
  51.     for (size_t i = 0; i < m; i++){
  52.         for (size_t j = 0; j < m; j++){
  53.             matrix[i][j] = I[i][j];
  54.         }         
  55.     }
  56. }
  57.  
  58. int main(int argc, char const *argv[]){
  59.     ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  60.     // #ifndef ONLINE_JUDGE
  61.     //     freopen("inp.txt", "r", stdin);
  62.     //     freopen("out.txt", "w", stdout);
  63.     // #endif
  64.  
  65.     int t;
  66.     cin>>t;
  67.  
  68.     ll m, n;
  69.  
  70.     while(t--){
  71.         cin>>m>>n;        
  72.  
  73.         for (size_t i = 0; i < m; i++){
  74.             for (size_t j = 0; j < m; j++){
  75.                 cin>>matrix[i][j];
  76.             }    
  77.         }
  78.  
  79.         power(m, n);
  80.  
  81.         for (size_t i = 0; i < m; i++){
  82.             for (size_t j = 0; j < m; j++){
  83.                 cout<<matrix[i][j]<<" ";
  84.             }    
  85.             cout<<"\n";
  86.         }        
  87.     }
  88.  
  89.     return 0;
  90. }
Success #stdin #stdout 0s 4560KB
comments (?)
stdin
copy 
2
2 3
1 0 
1 1 
3 3
1 0 4 
1 2 2 
0 4 4
stdout
copy 
1 0 
3 1 
17 112 116 
15 88 100 
28 144 160
https://ideone.com/tHLsrE
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!