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 !!! .
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]=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;
}
}
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 .
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…