Encara més seqüències de bits P84293


Statement
 

pdf   zip

thehtml

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++