I tried to solve this problem by linear recurrence
still I am not able to pass 2nd and 3rd test case
I am getting this message
TESTCASE # 2 : wrong-answer (Time: 2.07 s)
please help, thank you
code:
#include
#include
#define ll long long
#define REP(i,n) for(ll i=1;i<=n;i++)
using namespace std;
typedef vector<vector > matrix;
const ll MOD = 1000000009;
const int k=2;
matrix multiply(matrix A , matrix B){
matrix C(k+1, vector(k+1));
REP(i,k) REP(j,k) REP(l,k)
C[i][j]=(C[i][j]+(A[i][l]*B[l][j]))%MOD;
return C;
}
matrix power(matrix A,int p){
if(p==1){
return A;
}
if(p&1){
return(multiply(A,power(A,p-1)));
}
matrix X = power(A,p/2);
return(multiply(X,X));
}
ll fib(ll N){
vector<ll> F1(k+1);
F1[1]=1;
F1[2]=1;
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= power(T,N-1);
// First row 1st element is a ans of T^N-1 * F1
ll res=0;
REP(i,k){
res=(res+T[1][i]*F1[i])%MOD;
}
return res;
}
int main(){
ll t,n;
cin>>t;
while(t--){
cin>>n;
cout<<fib(n)<<'\n';
}
}