Because of necessary software maintenance, Jutge.org may not fully work on the 7 of may, from 8 to 10 CEST.
Encara més seqüències de bits P84293
Calculeu el nombre de seqüències diferents de longitud n, formades només per zeros i uns, i tals que no tenen més de dos uns consecutius.
Entrada
L’entrada consisteix en diversos casos, cadascun amb un natural n entre 0 i 109.
Sortida
Per a cada cas, escriviu quantes seqüències diferents de n bits no tenen més de dos uns consecutius, mòdul 109 + 7.
Pista
Una matriu es pot elevar a un natural x fent només Θ(logx) productes de matrius.
Public test cases
Input
0 1 2 3 4 5 20 1000 123456789
Output
1 2 4 7 13 24 223317 475857792 357891500
Information
- Author
- Pol Mauri
- Language
- Catalan
- Other languages
- English
- Official solutions
- C++
- User solutions
- C++