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.

$\endgroup$
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$.

$\endgroup$
  • $\begingroup$ Thank you. Very cool and indeed trivial. I'm sad not to notice this fact myself. $\endgroup$ – Igor Mar 11 '18 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 Mar 11 '18 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 Mar 12 '18 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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