fork download
copy 
  1. /*
  2. By WIL
  3. */
  4. #include <stdio.h>
  5. #include <iostream>
  6. #include <memory.h>
  7. #include <algorithm>
  8. #include <queue>
  9. #include <vector>
  10. #include <map>
  11. #include <math.h>
  12. #include <stack>
  13. #include <limits.h>
  14.  
  15. using namespace std;
  16. #define zero(x) memset(x,0,sizeof(x))
  17. #define mone(x) memset(x,-1,sizeof(x))
  18. #define ll long long
  19. #define base 31
  20. #define mod 10
  21. #define X first
  22. #define Y second
  23. #define fo(i,n) for(int i=0;i<n;i++)
  24. #define foo(i,n) for(int i=1;i<=n;i++)
  25. #define fa(i,I,n) for(int i=I;i<n;i++)
  26. #define sz(x) x.size()
  27. #define pb push_back
  28. #define endl '\n'
  29. int n,m;
  30. struct matInt{
  31.     int t;
  32.     int arr[31][31];
  33.     matInt(int T){
  34.         t=T;
  35.         fo(i,t)fo(j,t)arr[i][j]=0;
  36.     }
  37.     matInt(){
  38.         t=30;
  39.         fo(i,t)fo(j,t)arr[i][j]=0;
  40.     }
  41. }I,O;
  42. matInt operator+(matInt o,matInt p){
  43.     int t=o.t;
  44.     matInt ret=matInt(t);
  45.     fo(i,t)fo(j,t)ret.arr[i][j]=(o.arr[i][j]+p.arr[i][j])%mod;
  46.     return ret;
  47. }
  48. matInt operator*(matInt o,matInt p){
  49.     int t=o.t;
  50.     matInt ret=matInt(t);
  51.     fo(i,t)fo(j,t)fo(k,t){
  52.         ret.arr[i][j]+=(o.arr[i][k]*p.arr[k][j])%mod;
  53.         ret.arr[i][j]%=mod;
  54.     }
  55.     return ret;
  56. }
  57. struct mat{
  58.     int t;
  59.     matInt arr[2][2];
  60.     mat(int T){
  61.         t=T;
  62.         fo(i,t)fo(j,t)arr[i][j]=O;
  63.     }
  64. };
  65. mat operator*(mat o,mat p){
  66.     int t=o.t;
  67.     mat ret=mat(t);
  68.     fo(i,t)fo(j,t)fo(k,t){
  69.         ret.arr[i][j]=ret.arr[i][j]+(o.arr[i][k]*p.arr[k][j]);
  70.     }
  71.     return ret;
  72. }
  73. mat pot(mat a,int b){
  74.     //if(b==0)return I;
  75.     if(b==1)return a;
  76.     mat c=pot(a,b/2);
  77.     c=c*c;
  78.     if(b&1)return c*a;
  79.     return c;
  80. }
  81. int t;
  82. int main(){
  83.     scanf("%d",&t);
  84.     O=matInt(30);
  85.     I=matInt(30);
  86.     fo(i,30)I.arr[i][i]=1;
  87.     int cas=1;
  88.     while(t--){
  89.         //cout<<"S\n";
  90.         scanf("%d%d",&n,&m);
  91.         matInt A=matInt(n);
  92.         fo(i,n)fo(j,n){
  93.             int v;
  94.             scanf("%d",&v);
  95.             A.arr[i][j]=v%mod;
  96.         }
  97.         O.t=I.t=n;
  98.         mat me=mat(2);
  99.         me.arr[0][0]=I;
  100.         me.arr[0][1]=I;
  101.         me.arr[1][0]=O;
  102.         me.arr[1][1]=A;
  103.         me=pot(me,m);
  104.         //fo(i,n){fo(j,n)cout<< me.arr[0][1].arr[i][j] <<" ";cout<<endl;}
  105.         matInt sol=(A*me.arr[0][1]);
  106.         printf("Case %d:\n",cas++);
  107.         fo(i,n){fo(j,n)printf("%d",sol.arr[i][j]);printf("\n");}
  108.     }
  109.     return 0;
  110. }
  111.  
Success #stdin #stdout 0s 3268KB
comments (?)
stdin
copy 
2
3 2
1 4 6
6 5 2
1 2 3
3 10
1 4 6
6 5 2
1 2 3
stdout
copy 
Case 1:
208
484
722
Case 2:
868
620
546
https://ideone.com/Hmg4sA
language:
C++ (gcc 8.3)
created:
8 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!