Totxanes P88430


Statement
 

pdf   zip

thehtml

Disposeu d’un nombre il·limitat de totxanes 3 × 1. Podeu posar cada totxana verticalment o horitzontalment. De quantes maneres podeu cobrir un rectangle n × 3? Les totxanes no poden solapar-se ni sortir del rectangle.

Per exemple, per a n=4 hi ha tres maneres (mireu el pdf de l’enunciat per veure-ho bé):

unit=0.45cm

(34,8) fillstyle=hlines hatchcolor=red (1,1)(3,7) hatchcolor=green (3,1)(5,7) hatchcolor=orange (5,1)(7,7) hatchcolor=blue (7,1)(9,7) -(1,1)(1,7) -(3,1)(3,7) -(5,1)(5,7) -(7,1)(7,7) -(9,1)(9,7) -(1,1)(9,1) -(1,3)(9,3) -(1,5)(9,5) -(1,7)(9,7) hatchcolor=red (13,1)(19,3) hatchcolor=green (13,3)(19,5) hatchcolor=orange (13,5)(19,7) hatchcolor=blue (19,1)(21,7) -(13,1)(13,7) -(15,1)(15,7) -(17,1)(17,7) -(19,1)(19,7) -(21,1)(21,7) -(13,1)(21,1) -(13,3)(21,3) -(13,5)(21,5) -(13,7)(21,7) hatchcolor=red (27,1)(33,3) hatchcolor=green (27,3)(33,5) hatchcolor=orange (27,5)(33,7) hatchcolor=blue (25,1)(27,7) -(25,1)(25,7) -(27,1)(27,7) -(29,1)(29,7) -(31,1)(31,7) -(33,1)(33,7) -(25,1)(33,1) -(25,3)(33,3) -(25,5)(33,5) -(25,7)(33,7)

Entrada

L’entrada consisteix en diverses n entre 1 i 105.

Sortida

Per a cada n donada, escriviu una línia amb el resultat. Com que el resultat pot ser molt gran, (per exemple, per a n=50 ja seria 122106097), per evitar sobreiximents feu tots els càlculs mòdul 100000007 (108 + 7).

Pista

Si repetiu càlculs la vostra solució pot ser massa lenta.

Public test cases
  • Input

    1
    3
    4
    10
    49
    50
    60
    100000
    60
    

    Output

    1
    2
    3
    28
    83316385
    22106090
    82215970
    77894047
    82215970
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++