FIbonnaci using matrix recurrence

general
, ,
1

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…

2

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
3

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

4

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 .

5

see this problem…http://www.hackerearth.com/problem/algorithm/unknown-name/description/ …

6

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

7

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)
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]=1;
f1[2]=2;
matrix T(K+1,vector<ll>(K+1));
T[1][1]=0;
T[1][2]=1;
T[2][1]=1;
T[2][2]=1;

if(n==1)
return 1;

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

FOR(i,K)
ans=(ans+T[1][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;
}
  }
8

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 .

9

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

1 Like