Doubt in undrestanding code for matrix exponation

#1

Hi, I can’t understand the code about matrix exponation.

I have some questions

We have the vector b and c why we declare it again and copy the same elements on that?

5

and when copying elements from array c to transformation matrix he wrote this code can someone explain how this code works?

   if(n&1){
           return pow(a,multipy(a,p-1));
    }

can we write this down line instead of this line?

if(n&1){
      vector<vector<ll>> s= pow(a,p/2);
      return multiply(s,s);
}

How does this multipication matrix do?

why we declare 2d array c? I thought that the answer of multiplication of to matrix would be one dimensional
Multipication Function:

    vector<vector<ll> > multiply(vector<vector<ll> > A,vector <vector<ll>>B){
    	vector<vector<ll>> C(k+1,vector<ll>(k+1));
    	for(int i=1;i<=k;++i){
            	for(int j=1;j<=k;++j){
             		for(int x=1;x<=k;++x){
    				c[i][j] = (c[i][j] + (A[i][x]*B[x][j])%MOD)%MOD;
             		}
        		}
    	}
    	return C;
    }

Sorry for a lot of question Thanks.

#2

Please Help . This question is about competeive programming

#3

Reason for point 1.
He used standard approach to solve Matrix Exponentiation
For Solving Matrix Exponentiation you need
F1=T^(x) * F0
Here F1 is required matrix
T=Transformation Matrix
X= Power of transformation Matrix depending on F1
F0= Base Matrix
So, He just converted the given values in the Upper format
So he just wrote F0
Then find T matrix
then he will find x
and then he will solve the math.
He is just converting the given values according to upper given format.
I know you can handle it without F0 by directly using b vector
bt he used it just to make it look simple as above given equation

#4

For your query about
when copying elements from array c to transformation matrix he wrote this code can someone explain how this code works?

Can u mention problem link or name?

#5

For Multiply , you are saying that we don’t need C matrix as 2D matrix because C matrix will be 1 D matrix.
But Multiply Function is also used in power function Code where you call multiply to generate a matrix of k*k matrix.

#6

This code complexity O(n)

if(n&1){
return pow(a,multipy(a,p-1));
}

This code complexity O(n logn)
if(n&1){
vector<vector> s= pow(a,p/2);
return multiply(s,s);
}

#7

Hi,
For Your last reply why that is O(n) and My code is O(log n)?
Thank You For Support

#8

you have not not given me complete code.
It is just a guess from partial code
if(n&1){
return pow(a,multipy(a,p-1));
}
If I get your complete code,
then I can tell u the proper complexity.

For computing x^n
if n is even then ans=pow( (x * x),(n/2))
else ans= x * (pow(x,n-1))
if you are using this logic then yess your complexity is O(n log n )

#9

Yes im using this logic but i think your code is wrong if n is even
It must be:
int ind = pow(x,n/2)
return ind*ind;
And it is not clear for me how you make the transformation matrix with matrix c please help me. And how the code for it works.

#10

No my code is right .It is just written in some different way.

gallery
gallery720×422 57.1 KB

#11

Can u mention problem name so that I can make Transformation matrix for it