Matrix Exponenetiation

#1

vector<vector> matrix_expo(vector<vector> A, int p){

vector<vector<ll>> res(A.size(),vector<ll>(A.size(),1));	

while(p){

	if(p&1)
		res = matrix_multiply(res, A);

	A = matrix_multiply(A, A);
	p >>= 1;
}

return res;

}

Please explain the error in the code for matrix iterative exponentiation as it gives incorrect output.

#2

there is error in vector initalization…follow this generic code of matrix exponentation.

#3 
    #define lop(i, a, b)    for (int i = a; i < b; i++)

    const int M = 5;
    struct mat_expo
    {
         int m[M][M];

         mat_expo() { memset(m, 0, sizeof m); }

         void eye() { lop(i, 0, M) m[i][i] = 1; }

         mat_expo operator*(const mat_expo &a) const
         {
              mat_expo r;
              lop(i, 0, M) lop(j, 0, M) lop(k, 0, M)
                           r.m[i][j] = (r.m[i][j] + m[i][k] * 1ll * a.m[k][j]) % mod;
              return r;
         }
    };
    mat_expo getans(mat_expo bb, int k)
    {
         mat_expo aa;
         aa.eye();
         while (k > 0)
         {
              if (k & 1) aa = aa * bb;
              bb = bb * bb;
              k /= 2;
         }
         return aa;
    }
#4

Got it, but can you explain why the diagonal elements should be initialized with 1?

#5

so that it will become identity matrix.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.