Puzzle horitzontal P74317


Statement
 

pdf   zip

thehtml

Disposeu d’una col·lecció infinita de peces 1 × 1, 1 × 2 i 2 × 2, i heu d’omplir totalment un rectangle 2 × n. De quantes maneres ho podeu fer?

Per exemple, aquesta és una de les moltes maneres per a n = 7:

unit=1.2cm (9,4)

(1,1)(1,0)7 (1,1)(0,1)2 (8,3)(-1,0)7 (8,3)(0,-1)2

(2,1)(0,1)2 (2,2)(1,0)1 (3,1)(0,1)1 (3,2)(1,0)1 (4,2)(0,1)1 (4,2)(1,0)1 (5,1)(0,1)2 (7,1)(0,1)2 (7,2)(1,0)1

Entrada

L’entrada consisteix en diversos casos, cadascun amb una n entre 1 i 104.

Sortida

Per a cada cas, escriviu el nombre de maneres d’omplir un rectangle 2 × n. Com que aquest nombre pot ser molt gros, feu els càlculs mòdul 108 + 7.

Observació

Potser us pot ser útil calcular també una quantitat semblant a la que demana el problema.

Public test cases
  • Input

    1
    2
    3
    4
    10000
    

    Output

    2
    8
    26
    90
    52273134
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++ Java