Fast Fibonacci Question

#1

#include
#include
using namespace std;

#define ll unsigned long long
#define MOD 1000000007
static int k = 2;

vector<vector > multiply(vector<vector > A,vector<vector > 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;

}

vector<vector > pow(vector<vector >A,ll p){
if(p==1)
return A;
if(p&1)
return multiply(A,multiply(pow(A,p/2),pow(A,p/2)));
else
{
// vector<vector > X = pow(A,p/2);
// return multiply(X,X);
return multiply(pow(A,p/2),pow(A,p/2));
}
}

int main(){

int t;
cin>>t;
int n;
while(t--){
    cin>>n;
    if(n==1||n==2)
    cout<<1;
    else{
        vector<int> F1(k+1);
        F1[1]=1;
        F1[2]=1;

        vector<vector<ll> > T(k+1,vector<ll>(k+1));
        T[1][1]=0;
        T[1][2]=1;
        T[2][1]=1;
        T[2][2]=1;

        T= pow(T,n-1);

        ll res=0;
        // for(int i=1;i<=k;i++){
        // res = (res + (T[1][i]*F1[i])%MOD)%MOD;
        // }
        // cout<<res<<endl;
		res=T[1][2];
		cout<<res<<endl;

    }

}

return 0;

}
Kindly check why the submission is giving TLE, isnt matrix exponentiation the most efficient method?

#2

It must be because of the way you are passing vectors in the function as copying them consumes quite a time. Try either with passing it as reference or use arrays.

#3

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.