 # 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 .

Happy Coding !!! .

1 Like

Here is my code …i dont think i missed any case… ``````#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)
C[i][j]=(C[i][j]+A[i][k]*B[k][j])%MOD;
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);
f1=1;
f1=2;
matrix T(K+1,vector<ll>(K+1));
T=0;
T=1;
T=1;
T=1;

if(n==1)
return 1;

T=_pow(T,n-1);
ll ans=0;

FOR(i,K)
ans=(ans+T[i]*f1[i])%MOD;
return ans;

}

int main()
{
long long int t;
long long int N;
cin>>t;
while(t--)
{
scanf("%lld",&N);
ll val=solve(N);
cout<<val<<endl;
}
}``````

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 .

used the same logic bro …still its not working … 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…http://www.hackerearth.com/problem/algorithm/unknown-name/description/

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

got it …needed to pass matrix by reference instead of by value… 1 Like