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