Matrix Exponentiation

namespace matrix{
    #define size 105 ///Maximum size of the matrix
    #define wint int ///datatype to use (int,long long etc)
    wint mat[size][size],tmp[size][size],res[size][size];
    wint MOD;
    int n;
    void init(int _n,wint _MOD){ ///initialization, _n=size of the square matrix , _MOD=mod value
        n=_n;
        MOD=_MOD;
        memset(mat,0,sizeof (mat));
        memset(tmp,0,sizeof (tmp));
        memset(res,0,sizeof (res));
    }
    void mul(wint r[][size],wint a[][size],wint b[][size]) {
        int i,j,t;
        for(i=0; i<n; i++) for(j=0; j<n; j++) {
            long long val=0;
            for(t=0; t<n; t++) val+=1LL*a[i][t]*b[t][j];
            tmp[i][j]=val%MOD;
        }
        memcpy(r,tmp,n*size*sizeof(tmp[0][0]));
    }
    void mPow(wint r[][size],wint a[][size],wint p) {
        int i;
        if (p<0) return;
        memset(r,0,sizeof(r));
        for(i=0; i<n; i++) r[i][i]=1;
        while(p>0) {
            if(p&1) mul(r,r,a);
            mul(a,a,a); p>>=1;
        }
    }
    void pow(wint p){
        mPow(res,mat,p);
        memcpy(mat,res,n*size*sizeof(tmp[0][0]));
    }
    void print(wint pp[][size]){
        int i,j;
        for(i=0; i<n; i++){
            for(j=0; j<n; j++) printf(" %09d",pp[i][j]);
            printf("\n");
        }
    }
}

Go Back

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s