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 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

There are no comments at the moment.