FIbonnaci using matrix recurrence

I am using the matrix recurrence method for finding out the fibonnaci series upto n=10^15…it results in TLE for higher exponents…is there any other method faster than this…plz do suggest…

For matrix multiplication you should use fast exponentation .

A^p = A , if p = 1,

A^p = A .A^p-1, if p is odd,

A^p = X^2 , where X = A^p/2 , otherwise.

Check this link for more help .

If you find my answer useful please upvote and accept it as right answer .
Happy Coding !!! .

1 Like

used the same logic bro …still its not working …:frowning:

Matrix Multiplication in O(n^3) . for fibonnaci size in 2*2 . therefore matrix multiplcation in O(8) . and power is O(log(n)) . So overall time complexity is O(8 * log(n) ) . How can then it result in TLE .

see this problem…

337 submitted and only 21 AC? No good…

Try to take care of the cases N=0 and N=1 separatedly…And maintain the recurrence for N > 2 only… Your logic is correct so the base cases might be the only thing you are missing…Also check types as N=10^15 might need long long int as argument for the recurrence

Here is my code …i dont think i missed any case…:confused:

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=1;i<=n;i++)
#define ll long long 
#define matrix vector< vector<ll> >
#define MOD 1000000007
const int K=2;

matrix mul(matrix A,matrix B)
matrix C(K+1,vector<ll>(K+1));
FOR(i,K) FOR(j,K) FOR(k,K)
return C;

matrix _pow(matrix A, ll p)
if (p == 1)
    return A;
    if (p % 2)
    return mul(A, _pow(A, p-1));
    matrix X = _pow(A, p/2);
    return mul(X, X);

ll solve(ll n)
vector<ll> f1(K+1);
matrix T(K+1,vector<ll>(K+1));

return 1;

ll ans=0;

return ans;


 int main()
long long int t;
long long int N;
	ll val=solve(N);

Your algo seems correct , there might be problem in the question , as kuruma pointed , out of 337 submitted only 21 AC , something seems strange or they want more optimization .

got it …needed to pass matrix by reference instead of by value…:smiley:

1 Like