Informatyczny kącik olimpijski

Maszyna Fibonacciego

W tym kąciku zajmiemy sią zadaniem z finału Potyczek Algorytmicznych 2009.

Weźmy funkcją $F$ zwracającą liczby Fibonacciego, tzn. $F(0) = 0,F(1) = 1$ oraz $|F(m) = F(m − 1) + F(m − 2)$ dla $m ⩾ 2.$ Mamy ciąg rejestrów $|(i1,i2,...,in),$ początkowo ustawionych na zera. W zadaniu chodzi o zaimplementowanie dwóch operacji:

dla podanych $a$ i $|b$ dodanie jedynki do każdego z rejestrów $ia,ia+1,...,ib− 1,ib,$
dla podanych $a$ i $b$ wypisanie reszty z dzielenia warto/sci $F(ia) + F(ia+1) +...+ F(ib−1)+ F(ib)$ przez $P = 109 + 7.$

***

Cały artykuł dostępny jest w wersji do druku: (64 KB)