Submit solution
Points:
100 (partial)
Time limit:
3.0s
Memory limit:
256M
Author:
Problem type
Allowed languages
C, C++, Python
Diga cuántos ciclos simples distintos existen en un grafo completo no dirigido de \(n (3 \leq n \leq 2000)\) nodos, como la respuesta puede ser demasiado grande imprímala módulo \(10^9+7\).
Un grafo completo no dirigido es un grafo que por cada par de nodos distintos, existe una arista entre ellos.
Un ciclo simple es una secuencia de nodos \(v_{0}, v_{1}, ... , v_{k-1}\), con \(k \geq 3\), de que cumpla las siguientes condiciones:
- Todos los nodos del ciclo son distintos
- Los nodos \(v_{i}\) y \(v_{(i+1) mod (k)}\) están conectados por una arista, dicha arista forma parte del ciclo
- Todas las aristas que forman parte del ciclo son distintas
Dos ciclos \(a\) y \(b\) se consideran distintos si alguna de las siguientes condiciones se cumple:
- Existe un nodo que se encuentra en \(a\) y no en \(b\), o existe un nodo que se encuentra en \(b\) y no en \(a\).
- Existe una arista que se encuentra en \(a\) y no en \(b\), o existe una arista que se encuentra en \(b\) y no en \(a\).
Constantes
\(1 \leq T \leq 1000\), la cantidad de casos a procesar
\(1 \leq n \leq 2000\), la cantidad de nodos del grafo en cada caso.
Puntuación
- Subtarea 1, \(T \leq 6, n \leq 8\) (30 puntos).
- Subtarea 2, sin restricciones adicionales (70 puntos).
Ejemplo de entrada
4
3
4
5
2000
Ejemplo de salida
1
7
37
320019990
Comments