problem link:- https://www.codechef.com/problems/KFIB

please give some hint to solve this problem

there will be exactly k 1’s in the solution. so first, create a list `list_ = [1]*k`

Then, append `sum(list_[i:]) in list_ for i in range(n - k)`

1 Like

Here’s my trial code and submission link

```
n,k=map(int,input().split())
l=[1]*k
for i in range(n-k):
l.append(sum(l[i:])%1000000007)
print(l[-1])
```

1 Like

**The Problem in Short:**

Given 2 integers N and K, we need to find the N^{th} term modulo 10^{9}+7 for the series:

T(N, K) = 1 if N <= K and T(N, K) = T(N-1, K) + T(N-2, K) + T(N-3, K) … + T(N-K, K) if N > K

**Some Observations**

- K does not change in the relation given in the question, implying it to be a static parameter.
- If the given N<=K, we can simply return 1 as the answer.
- If the given N>K, the first K terms of the series would be 1.

We can make an array where series[i] will store the i^{th} term of the series.

So with all these basic observations, we can loop from K+1 till N(both inclusive).

For each i from K+1 till N, the i^{th} term can be found out by adding all the terms from i-1 to i-K (as specified in the question).

Then perform mod operations as specified in the question.

The answer would be series[N]

For complete implementation, this is the link to my code.

Submission Link

1 Like

quite well explained. I used a similar approach. The difference in the language gives a difference of 132 lines of code

and also 17 times slower.

1 Like

Not really 132 lines. I’ve used C++ and my code has a template with some functions, some #define type definitions, and a lot more.

The core logic is written in the main function and is not that big…

If the given N>K, the first K terms of the series would be 1.

can you explain this

for example if i take (10,2)

then (10,2)=(9,2)+(8,2)

how can (9,2) and (8,2) equals 1

You have interpreted the statement in the wrong way.

(10,2) is the 10^{th} term of the series.

(1,2) will be the 1^{st} term

(2,2) will be the 2^{nd} term

In both (1,2) and (2,2) we have N<=K

I hope your doubt was cleared