Otro problema de conteo (III)
Submit solution
Points:
100 (partial)
Time limit:
3.0s
Memory limit:
256M
Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Python, Swift, VB
Diga cuántos ciclos simples distintos existen en un grafo completo no dirigido de nodos, como la respuesta puede ser demasiado grande imprímala módulo .
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 , con , de que cumpla las siguientes condiciones:
- Todos los nodos del ciclo son distintos
- Los nodos y están conectados por una arista, dicha arista forma parte del ciclo
- Todas las aristas que forman parte del ciclo son distintas
Dos ciclos y se consideran distintos si alguna de las siguientes condiciones se cumple:
- Existe un nodo que se encuentra en y no en , o existe un nodo que se encuentra en y no en .
- Existe una arista que se encuentra en y no en , o existe una arista que se encuentra en y no en .
Constantes
, la cantidad de casos a procesar
, la cantidad de nodos del grafo en cada caso.
Puntuación
- Subtarea 1, (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