plz somebody help me in getting this right .

I did dp[i] equals dp[i-2]+dp[i-3]

```
#include <iostream>
using namespace std;
int main() {
long int n,i;
cin>>n;
while(n--){
long int t;
cin>>t;
if(t==1){
cout<<"0"<<endl;
}
long int dp[t+1]={0};
dp[2]=1;
dp[3]=1;
for(i=4;i<=t;i++)
{
if(i==4)
dp[i]=dp[i-2];
else
dp[i]=(dp[i-2])+(dp[i-3]);
dp[i]=dp[i]%1000000009;
}
cout<<(dp[t])<<endl;
}
return 0;
}
```

I haven’t read the question, but I have never seen the answer asked modulo 10^9 + 9. You should post the question link when asking a doubt.

You are printing 2 values when `t==1`

. You can just remove that and your code will become correct. Try minimising the number of `if`

conditions. Also, it’s not good practice to have 10^9 + 9 written explicitly, it’s better to put it in a constant variable.

##
Corrected code

```
#include <iostream>
using namespace std;
const int p = 1e9 + 9;
int main() {
long int n;
cin>>n;
while(n--){
long int t;
cin>>t;
long int dp[t+1]={0};
dp[2]=1;
dp[3]=1;
for(int i=4;i<=t;i++){
dp[i]=(dp[i-2])+(dp[i-3]);
dp[i]=dp[i]%p;
}
cout<<(dp[t])<<endl;
}
return 0;
}
```

Also your code isn’t fast enough.

##
Spoiler

You can precompute the dp and then answer all of them in O(1).

Alternatively you can use matrix exponentiation.

\begin{bmatrix} 1 & 0 & 1\end{bmatrix} \times
\begin{bmatrix} 0 & 0 & 1\\ 1 &0 &1\\ 0 & 1 &0 \end{bmatrix}^t. The first term of the resultant matrix will be dp[t]

2 Likes

thank you very much !!

I ll llearn matrix exponentiation

thanks!

while precomputing should i comput it for all 10^6 possible queries

?

@everule1 How did you come up with that matrix form for the recurrence relation? I also want to learn the technique to convert a recurrence relation into matrix form.