Número de caminos P30076
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).
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
- Author
- Salvador Roura
- Language
- Spanish
- Official solutions
- C++
- User solutions