Recuento de grafos distintos que se pueden formar con N vértices

Dado un número entero N que es el número de vértices. La tarea es encontrar el número de gráficos distintos que se pueden formar. Dado que la respuesta puede ser muy grande, imprima la respuesta % 1000000007 .
Ejemplos: 
 

Entrada: N = 3 
Salida: 8
Entrada: N = 4 
Salida: 64 
 

Acercarse: 
 

• El número máximo de aristas que puede contener un gráfico con N vértices es X = N * (N – 1) / 2.
• El número total de grafos que contienen 0 aristas y N vértices será ^X C ₀
• El número total de grafos que contienen 1 arista y N vértices será ^X C ₁
• Y así sucesivamente desde un número de aristas 1 a X con N vértices
• Por lo tanto, el número total de grafos que se pueden formar con n vértices será:
  ^X C ₀ + ^X C ₁ + ^X C ₂ + … + ^X C _X = 2 ^X .

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
// Function to return (x^y) % MOD
// in O(log(y))
long long power(long long x,
                long long y,
                const int& MOD)
{
    long long res = 1;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % MOD;
        x = (x * x) % MOD;
        y /= 2;
    }
    return res;
}
 
// Function to return the count of distinct
// graphs possible with n vertices
long long countGraphs(int n)
{
 
    // Maximum number of edges for a
    // graph with n vertices
    long long x = n * (n - 1) / 2;
 
    // Function to calculate
    // (2^x) % mod
    return power(2, x, MOD);
}
 
// Driver code
int main()
{
    int n = 5;
 
    cout << countGraphs(n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
    static final int MOD = (int)1e9 + 7;
     
    // Function to return (x^y) % MOD
    // in O(log(y))
    static long power(long x,
                      long y)
    {
        long res = 1;
        while (y > 0)
        {
            if ((y & 1) != 0)
                res = (res * x) % MOD;
            x = (x * x) % MOD;
            y /= 2;
        }
        return res;
    }
     
    // Function to return the count of distinct
    // graphs possible with n vertices
    static long countGraphs(int n)
    {
     
        // Maximum number of edges for a
        // graph with n vertices
        long x = n * (n - 1) / 2;
     
        // Function to calculate
        // (2^x) % mod
        return power(2, x);
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 5;
     
        System.out.println(countGraphs(n));
    }
}
 
// This code is contributed by AnkitRai01

MOD = int(1e9 + 7)
 
# Function to return the count of distinct
# graphs possible with n vertices
def countGraphs(n):
 
    # Maximum number of edges for a
    # graph with n vertices
    x = (n *( n - 1 )) //2
     
    # Return 2 ^ x
    return (pow(2, x, MOD))
 
# Driver code
n = 5
print(countGraphs(n))

// C# implementation of the approach
using System;
 
class GFG
{
    static int MOD = (int)1e9 + 7;
     
    // Function to return (x^y) % MOD
    // in O(log(y))
    static long power(long x, long y)
    {
        long res = 1;
        while (y > 0)
        {
            if ((y & 1) != 0)
                res = (res * x) % MOD;
            x = (x * x) % MOD;
            y /= 2;
        }
        return res;
    }
     
    // Function to return the count of distinct
    // graphs possible with n vertices
    static long countGraphs(int n)
    {
     
        // Maximum number of edges for a
        // graph with n vertices
        long x = n * (n - 1) / 2;
     
        // Function to calculate
        // (2^x) % mod
        return power(2, x);
    }
     
    // Driver code
    static public void Main ()
    {
        int n = 5;
     
        Console.Write(countGraphs(n));
    }
}
 
// This code is contributed by ajit.

<script>
 
// Javascript implementation of the approach
 
const MOD = 1000000000 + 7;
 
// Function to return (x^y) % MOD
// in O(log(y))
function power(x, y, MOD)
{
    let res = 1;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % MOD;
        x = (x * x) % MOD;
        y = parseInt(y / 2);
    }
    return res;
}
 
// Function to return the count of distinct
// graphs possible with n vertices
function countGraphs(n)
{
 
    // Maximum number of edges for a
    // graph with n vertices
    let x = parseInt(n * (n - 1) / 2);
 
    // Function to calculate
    // (2^x) % mod
    return power(2, x, MOD);
}
 
// Driver code
    let n = 5;
 
    document.write(countGraphs(n));
 
</script>

1024

Complejidad del tiempo: O(log(n ² ))

Espacio Auxiliar: O(1)