Collaret de perles (2) P89236


Statement
 

pdf   zip

thehtml

Volem fer un collaret amb perles blanques i negres, amb dues condicions:

  • No hi poden haver quatre o més perles blanques adjacents.
  • No hi poden haver dues o més perles negres adjacents.

Tingueu en compte que el collaret és circular, és a dir, la primera perla i l’última perla són adjacents. Per exemple, aquests són els sis collarets possibles amb quatre perles (una B indica una perla blanca, una N indica una perla negra):

BBBN BBNB BNBB NBBB BNBN NBNB

(Els quatre primers collarets i els dos últims en el fons són iguals, però en aquest problema els distingirem.)

Quants collarets amb n perles hi ha?

Entrada

L’entrada conté diversos casos, cadascun amb una n entre 2 i 1012.

Sortida

Per a cada n, escriviu el nombre de collarets de perles de mida n. Com que el resultat pot ser molt gros, feu els càlculs mòdul 108 + 7.

Puntuació

  • Cas A:  ‍ Casos amb n ≤ 15, com l’exemple d’entrada 1.  ‍25% Punts ‍
  • Cas B:  ‍ Casos amb n ≤ 30, com l’exemple d’entrada 2.  ‍25% Punts ‍
  • Cas C:  ‍ Casos amb n ≤ 105, com l’exemple d’entrada 3.  ‍25% Punts ‍
  • Cas D:  ‍ Casos de tot tipus, com l’exemple d’entrada 4  ‍25% Punts ‍
Public test cases

  • Input

    2
4
5
7

    Output

    3
6
5
14

  • Input

    20
30

    Output

    2091
95546

  • Input

    40
50
100000

    Output

    4367947
99685515
82193899

  • Input

    1000000
1000000000000

    Output

    25866620
56689144
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++