Matrix Exponentiation

Learning resource:
Fast exponentiation of numbers: http://machlearner.blogspot.in/2013/09/modular-exponentiation.html

Same concept can be applied to raise matrices to a power.

Implementation:

// If the original matrix is stored in a[][], matexp(n) calculates a^n.

#define DIM 10
#define MOD 1000000007
LL a[DIM][DIM],cpy[DIM][DIM];

void matmultiply(LL y[DIM][DIM])
{
    for(int i=0;i<DIM;i++)
        for(int j=0;j<DIM;j++)
        {
            cpy[i][j]=0;
            for(int r=0;r<DIM;r++)
                cpy[i][j]=(cpy[i][j] + a[i][r]*y[r][j]) % MOD;
        }
    memcpy(a,cpy,sizeof cpy);
}

void matexp(int n)
{
    if(n==1)
        return;
    else if(n%2==0)
    {
        matexp(n/2);
        matmultiply(a);
    }
    else
    {
        LL temp[DIM][DIM];
        memcpy(temp,a,sizeof a);
        matexp(n-1);
        matmultiply(temp);
    }
}