Número de caminos P30076


Statement
 

pdf   zip

thehtml

Considerad un tablero n × m con p casillas prohibidas. Os encontráis en la casilla (1, 1), que corresponde a la esquina superior izquierda, y debéis ir a la casilla (n, m), que corresponde a la esquina inferior derecha. Sólo podéis hacer movimientos hacia la derecha y hacia abajo, y no podéis pasar por las casillas prohibidas. ¿Cuántos caminos existen?

Entrada

La entrada consiste en diversos casos, cada uno con n, m y p, seguidas de los p pares de coordenadas de las casillas prohibidas, todas diferentes. Suponed n ≥ 1, m ≥ 1, y que la casilla inicial y la final son diferentes y no están prohibidas.

Salida

Para cada caso, escribid el número de caminos válidos módulo 109 + 7.

Puntuación

  • test-1:  ‍ Entradas donde n ≤ 5, m ≤ 5 y p = 0, como el Ejemplo 1.  ‍10 Puntos ‍
  • test-2:  ‍ Entradas donde n ≤ 1000, m ≤ 1000 y p = 0, como el Ejemplo 2.  ‍20 Puntos ‍
  • test-3:  ‍ Entradas donde n ≤ 30, m ≤ 30 y p ≤ 10, como el Ejemplo 3.  ‍30 Puntos ‍
  • test-4:  ‍ Entradas donde n ≤ 1000, m ≤ 1000 y p ≤ 10, como el Ejemplo 4.  ‍40 Puntos ‍

Pista

Los juegos de pruebas privados tienen muchos casos, y la solución esperada resuelve cada uno básicamente en coste Θ(p2).

Public test cases
  • Input

    2 3 0
    4 4 0
    1 5 0
    

    Output

    3
    20
    1
    
  • Input

    100 200 0
    1000 1000 0
    

    Output

    111899243
    965601742
    
  • Input

    4 4 2  2 2  2 3
    1 5 1  1 2
    20 15 3  4 10  8 3  18 11
    

    Output

    5
    0
    614117349
    
  • Input

    60 100 4  10 20  40 8  15 95  23 42
    1000 1000 3  5 7  400 500  123 987
    

    Output

    81493229
    47365937
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions