Otro problema de conteo (III).

View as PDF

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

There are no comments at the moment.