Secuencias feas P84321


Statement
 

pdf   zip

thehtml

En este problema, decimos que una secuencia de números es k-fea si tiene exactamente k pares de posiciones adyacentes con dos números consecutivos. Haced un programa que, dada una n, una k y m posiciones para las cuales ya se ha fijado el contenido, cuente el número de secuencias k-feas de tamaño ‍n formadas con números entre 0 y n − 1 y con el contenido fijado.

Entrada

La entrada consiste en diversos casos, cada uno con una n entre 1 y 100, seguida de una k entre 0 y n − 1, seguida de una m entre 0 y n, seguida de m pares i x, indicando que en la posición i tiene que haber una x. Suponed 0 ≤ y < n, 0 ≤ x < n, y que todas las i son diferentes.

Salida

Para cada caso, calculad cuantas secuencias k-feas de tamaño n formadas con números entre 0 y n − 1 hay con el contenido fijado, módulo 108 + 7.

Observación

Se pueden obtener 80 puntos sobre 100 si se pasan juegos de pruebas donde n ≤ 10.

Public test cases
  • Input

    2 1 0
    
    1 0 0
    
    3 1 1
    0 2
    
    3 1 2
    2 2
    0 2
    
    10 0 0
    
    100 99 0
    
    100 99 2
    0 0
    99 99
    
    79 56 2
    73 34
    60 57
    

    Output

    2
    1
    3
    0
    8825613
    83312187
    1
    46614250
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++