Advertisement
Infernale

Matrix power to the power of N

Oct 30th, 2018
473
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.92 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. int main(){
  4.     int tc,n;
  5.     const long long mod = 1000000007;
  6.     scanf("%d",&tc);
  7.     for(int i=1;i<=tc;i++){
  8.         scanf("%d",&n);
  9.         long long temp[n][n];
  10.         long long m[n][n];
  11.         long long r[n][n];
  12.         for(int j=0;j<n;j++){
  13.             for(int k=0;k<n;k++){
  14.                 scanf("%lld",&m[j][k]);
  15.             }
  16.         }
  17.         for(int b=0;b<n;b++){
  18.             for(int d=0;d<n;d++){
  19.                 r[b][d]=m[b][d];
  20.             }
  21.         }
  22.         for(int i=0;i<n-1;i++){
  23.             long long sum = 0;
  24.             for (int b=0;b<n;b++){
  25.                 for (int d=0;d<n;d++){
  26.                     for(int k=0;k<n;k++){
  27.                         sum += m[b][k]*r[k][d]%mod;
  28.                     }
  29.                     temp[b][d] = sum%mod;
  30.                     sum = 0;
  31.                 }
  32.             }
  33.             for (int b=0;b<n;b++){
  34.                 for (int d=0;d<n;d++){
  35.                     r[b][d] = temp[b][d];
  36.                 }
  37.             }
  38.         }
  39.         printf("Case #%d:\n",i);
  40.         for(int j=0;j<n;j++){
  41.             for(int k=0;k<n;k++){
  42.                 if(k==n-1){
  43.                     printf("%lld\n",r[j][k]%mod);
  44.                 }else{
  45.                     printf("%lld ",r[j][k]%mod);
  46.                 }
  47.             }
  48.         }
  49.     }
  50.     return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement