Matrix Expo Library / Contest Matrix Lib

/****************************************
              Zerus97
*****************************************/

#include <bits/stdc++.h>


#define loop(i,s,e) for(int i = s;i<=e;i++) //including end point

#define pb(a) push_back(a)

#define sqr(x) ((x)*(x))

#define CIN ios_base::sync_with_stdio(0); cin.tie(0);

#define ll long long

#define ull unsigned long long

#define SZ(a) int(a.size())

#define read() freopen("input.txt", "r", stdin)

#define write() freopen("output.txt", "w", stdout)


#define ms(a,b) memset(a, b, sizeof(a))

#define all(v) v.begin(), v.end()

#define PI acos(-1.0)

#define pf printf

#define sfi(a) scanf("%d",&a);

#define sfii(a,b) scanf("%d %d",&a,&b);

#define sfl(a) scanf("%lld",&a);

#define sfll(a,b) scanf("%lld %lld",&a,&b);

#define sful(a) scanf("%llu",&a);

#define sfulul(a,b) scanf("%llu %llu",&a,&b);

#define sful2(a,b) scanf("%llu %llu",&a,&b); // A little different

#define sfc(a) scanf("%c",&a);

#define sfs(a) scanf("%s",a);

#define getl(s) getline(cin,s);

#define mp make_pair

#define paii pair<int, int>

#define padd pair<dd, dd>

#define pall pair<ll, ll>

#define vi vector<int>

#define vll vector<ll>

#define mii map<int,int>

#define mlli map<ll,int>

#define mib map<int,bool>

#define fs first

#define sc second

#define CASE(t) printf("Case %d: ",++t) // t initialized 0

#define cCASE(t) cout<<"Case "<<++t<<": ";

#define D(v,status) cout<<status<<" "<<v<<endl;

#define INF 1000000000   //10e9

#define EPS 1e-9

#define flc fflush(stdout); //For interactive programs , flush while using pf (that's why __c )



#define CONTEST 1

using namespace std;

//CONTEST MATRIX LIB

#define GB 0

#define dim 4

#define mat vector<vector<int>>

mat GBv;

int idmat[] = //Each row
{
    1,0,1,1 ,
    1,0,0,0 ,
    0,1,0,0 ,
    0,0,0,1
};
mat assImat(int arr[]) // assign identity matrix
{
    mat X;



    int arridx = 0;

    vi rows;



    if(!rows.empty())
    {
        rows.clear();
    }

    loop(r,0,dim-1)
    {

        loop(c,0,dim-1)
        {
            rows.pb(arr[arridx]);

            arridx++;
        }
        X.pb(rows);
        rows.clear();


    }

    return X;

}

mat matmul(mat A,mat B,int ra,int ca,int rb,int cb)
{
    if(ca!=rb)
    {
        cout<<"ERR dim"<<endl;
        return GBv;
    }

    mat res;

    vi rows;

    loop(amr,0,ra-1) //ans matrix row
    {
        loop(amc,0,rb-1)
        {
            int rowi = 0;
            loop(crc,0,ca-1) //common row column
            {
                rowi+=A[amr][crc]*B[crc][amc];
            }

            rows.pb(rowi);

        }

        res.pb(rows);
        rows.clear();


    }

    return res;


}
mat expo(mat A, int row,int col,int p)
{
    if(p==1)
        return A;
    else if(p==2)
    {
        mat res = matmul(A,A,row,col,row,
                         col);
        return res;
    }
    else if(p%2==0)
    {
        mat halfp = expo(A,row,col,p/2);
        mat res = matmul(halfp,halfp,
                         row,col,row,col);
        return res;
    }
    else if(p%2==1)
    {
        mat halfp = expo(A,row,col,p/2);
        mat resp = matmul(halfp,halfp,
                          row,col,row,col);
        mat finres = matmul(resp,A,
                            row,col,row,col);
        return finres;
    }



}
void showmat(mat A,int row,int col)
{
    loop(r,0,row-1)
    {
        loop(c,0,col-1)
        cout<<A[r][c]<<" ";
        cout<<endl;
    }
}

int main()
{
    mat TT = assImat(idmat);

    showmat(TT,dim,dim);

    mat ans  = matmul(TT,TT,dim,dim,dim,dim);

    cout<<"----------"<<endl;

    showmat(ans,dim,dim);

    mat ans2 = expo(TT,dim,dim,2);
    
    cout<<"----------"<<endl;
    
    showmat(ans2,dim,dim);






    return 0;
}