2
$\begingroup$

Let's define the sequence of $k$-Fibonacci numbers as $$ F_i = 2^i, ~~ 0 \leq i \leq k-1 $$ $$ F_i = F_{i-1} + \dots + F_{i-k}, ~~ i \geq k $$

I have a problem which requires to compute $n$-th $k$-Fibonacci number modulo $10^9 + 7$ efficiently. $n$ can be as large as $10^6$, $k$ can have any value between $1$ and $n$, time limit is $1$ second.

When $k$ is small enough i can use matrix-power approach for computing $n$-th members of linear recurrent sequences. This requires $O(k^3 \log(n)$ operations which is not feasible when $k > 250$ since takes more than one second.

When $k$ is large but $n$ is small i can compute this exactly by definition with $O(nk)$ operations. This approach is also not feasible when $k,n \approx 10^5$ or larger.

So how can i compute them faster? I neither derived nor found on the web any useful formulas which allow to represent this recurrence with smaller depth. Thus i believe that it's more an algorithmic than combinatorial question.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

It's trivial to do in O (n), using the obvious formula $F_{i+1} = 2F_i - F_{i-k}$. Just write down the definition of $F_{i+1}$ and note that it is mostly (but not quite) the same as the definition of $F_i$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you. Very cool and indeed trivial. I'm sad not to notice this fact myself. $\endgroup$
    – Igor
    Commented Mar 11, 2018 at 18:17
  • 1
    $\begingroup$ It's easy for problems from problem websites because you know it can be done. You know there is a trick, and the question is just which one? $\endgroup$
    – gnasher729
    Commented Mar 11, 2018 at 19:29
  • 1
    $\begingroup$ You also know it can be done in one second, which means it can be done in 0.1 seconds with micro-optimisations, so for k, n ≈ 10^6 it can be done in less than 100n operations. Which means calculating F_n+1 should be quite simple. $\endgroup$
    – gnasher729
    Commented Mar 12, 2018 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.