fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. #define dbg(x) cout<<#x<<"="<<x<<" "
  5. #define nl cout<<"\n"
  6. #define fr(i,n) for(int i=0;i<n;i++)///#define part
  7. const int MOD=1e9+7;
  8. ll n,INV[100];struct matrix {ll arr[32][32];};////declaration part
  9. void print(matrix A){
  10.   fr(i,n){fr(j,n)cout<<A.arr[i][j]%MOD<<" ";cout<<endl;}
  11.   cout<<endl;}
  12. void takemod(ll &a){
  13.     if(a<0){
  14.         a*=-1;if(a>=MOD)a%=MOD;
  15.         if(a!=0)a=MOD-a;
  16.     }
  17.     else if(a>=MOD)a%=MOD;}////modulo part
  18. matrix mul(matrix &A,matrix &B){
  19.    matrix C;memset(C.arr,0,sizeof C.arr);
  20.    fr(i,n)fr(j,n)fr(k,n){
  21.     C.arr[i][j]+=A.arr[i][k]*B.arr[k][j];
  22.     takemod(C.arr[i][j]);
  23.     }
  24.    return C;}
  25. matrix add(matrix A,matrix B){matrix C;memset(C.arr,0,sizeof C.arr);fr(i,n)fr(j,n){C.arr[i][j]=A.arr[i][j]+B.arr[i][j];takemod(C.arr[i][j]);}return C;}
  26. ll tr(matrix A){ll res=0;fr(i,n){res+=A.arr[i][i];takemod(res);}return res;}
  27. ll fpow(ll a,ll b){
  28.     ll res=1;
  29.     while(b)
  30.     {
  31.         if(b&1){res*=a;takemod(res);}
  32.         a*=a;takemod(a);
  33.         b/=2;
  34.     }
  35.     return res;}
  36. ll inv(ll a){return fpow(a,MOD-2);}
  37. void asin(matrix &A,ll val){fr(i,n)fr(j,n)A.arr[i][j]=val;}
  38. void scale(matrix &A,ll val){takemod(val);fr(i,n)fr(j,n){A.arr[i][j]*=val;takemod(A.arr[i][j]);}}
  39. int main()
  40. {
  41.   for(int i=1;i<=50;i++)INV[i]=inv(i);
  42.   matrix g;cin>>n;
  43.   matrix gk[32];fr(i,n)gk[0].arr[i][i]=1;
  44.   ll coef[32],TR[32];coef[n]=1;
  45.   fr(i,n)fr(j,n){cin>>g.arr[i][j];takemod(g.arr[i][j]);}gk[1]=g;
  46.   for(int i=2;i<=30;i++)gk[i]=mul(g,gk[i-1]);
  47.   for(int i=0;i<=30;i++)TR[i]=tr(gk[i]);
  48.   for(int m=1;m<=n;m++){
  49.     ll temp=0;
  50.     for(int k=1;k<=m;k++){
  51.         temp+=coef[n-m+k]*TR[k];
  52.     }
  53.     temp*=inv(m);temp*=-1;
  54.     takemod(temp);
  55.     coef[n-m]=temp;
  56.   } 
  57.   matrix Adj_g;memset(Adj_g.arr,0,sizeof Adj_g.arr);
  58.   ll detg=coef[0];if(n&1)detg*=-1;takemod(detg);
  59.   for(int k=1;k<=n;k++){
  60.     matrix temp=gk[k-1];
  61.     scale(temp,coef[k]);
  62.     Adj_g=add(Adj_g,temp);
  63.   }
  64.   if(n&1);else fr(i,n)fr(j,n){Adj_g.arr[i][j]*=-1;takemod(Adj_g.arr[i][j]);}
  65.   dbg(coef[0]);dbg(detg);
  66.    print(mul(g,Adj_g));
  67. }
Success #stdin #stdout 0s 4432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
coef[0]=1 detg=1
https://ideone.com/d8JyBQ
language:
C++14 (gcc 8.3)
created:
4 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!