K Fibonacci WA

general
, , ,
1

I am getting WA for 2 subtasks in this question : https://www.codechef.com/problems/KFIB
My solution : https://www.codechef.com/viewsolution/18321444

Could someone please point out my mistake ?

1 Like
2

you can try 6 4
the ans should be 2

3

Shouldn’t the answer be 7 for 6 4 ? @ram_24

4

yeah you are right…Actually the problem is in a[i]=(((2*(a[i-1]%mod))%mod)-1)%mod; You shouldn’t do -1 rather you should subtract the a[i-k-1]th term from the exp… because the ith term will consist of last k terms and the (i+1)th term will contain its last k term which can easily be obtained by a[i]=((((a[i-1]+a[i-1])%mod)-a[i-k-1])%mod+mod)%mod;

1 Like
5

Okay, I’ll try with that change. Also, why did you use (+mod) in your modified equation ?

6

I tweaked the formula a little by adding a case. If i-k-1>k, I used a[I-k-1] else I subtracted 1. Thank you for the help. @ram_24