CODEWITHSUNDEEP
c++algorithmmathoptimizationmatrix
c_sharma
c_sharma

Reputation: 135

matrix exponentiation method for runtime optimization

Can anyone please explain or suggest some good tutorial for the method of matrix exponentiation in order to optimize the solution of the problem : great wall of byteland

The solution which I uploaded is based dynamic programming with this underlying equation : [ f(n) = f(n-1) + 4*f(n-2) + 2*f(n-3) ] but the solution is giving me Time Limit Exceeded Error.

This is the code I built :

    #include<iostream>
    #define num 1000000007
    using namespace std;
    int main(){
        int t;
        cin>>t;
        while(t--){
            int n;
            cin>>n;
            if(n<=3){
                switch(n){
                    case 1:
                        cout<<1<<endl;
                        break;
                    case 2:
                        cout<<5<<endl;
                        break;
                    case 3:
                        cout<<11<<endl;
                        break;
                }
            }
            else{
                int a=1 , b=5 , c=11 ;
                int next;
                for(int i=4;i<=n;i++){
                    next = (c + 4*b + 2*a)%num ;
                    a = b;
                    b = c;
                    c = next;
                }
                cout<<next<<endl;
            }
        }
        return 0;
    }

Please suggest the matrix exponentiation method for optimizing the run time of the solution.

Upvotes: 0

Views: 596

Answers (1)

Thomash
Thomash

Reputation: 6379

If you have a sequence defined by:

u(0) to u(d-1) are given
for n > d u(n)=a(1)*u(n-1)+…+a(d)*u(n-d)

then let A be the companion matrix defined by:

A(i,j) = a(d+1-j) if i = d
         1 if i+1 = j
         0 otherwise

and let uinit = transpose(u(0) … u(d-1))

You have A^n*uinit = transpose(u(n) … u(n+d-1)) (you can verify by yourself that A*transpose(u(n) … u(n+d-1)) = transpose(u(n+1) … u(n+d))).

Then you can compute A^n in O(Log(n)) and use it to compute u(n).

Upvotes: 2

Related Questions