Cuente subconjuntos no adyacentes a partir de números dispuestos en forma circular

Dado que N personas están sentadas en una cola circular numerada del 1 al N , la tarea es contar el número de formas de seleccionar un subconjunto de ellas de modo que no haya dos personas consecutivas sentadas juntas. La respuesta podría ser grande, así que calcula la respuesta módulo 10 ⁹ + 7 . Tenga en cuenta que un subconjunto vacío también es un subconjunto válido.

Ejemplos: 

Entrada: N = 2 
Salida: 3 
Todos los subconjuntos posibles son {}, {1} y {2}.

Entrada: N = 3 
Salida: 4  

Planteamiento: Encontremos la respuesta a valores pequeños de N .
N = 1 -> Todos los subconjuntos posibles son {}, {1} . 
N = 2 -> Todos los subconjuntos posibles son {}, {1}, {2} . 
N = 3 -> Todos los subconjuntos posibles son {}, {1}, {2}, {3} . 
N = 4 -> Todos los subconjuntos posibles son {}, {1}, {2}, {3}, {4}, {1, 3}, {2, 4} . 
Entonces la secuencia será 2, 3, 4, 7,… 
Cuando N = 5 el conteo será 11 y si N = 6 entonces el conteo será 18 . 
Ahora se puede observar que la secuencia es similar a una serie de Fibonacci comenzando desde el segundo término con los primeros dos términos, 3 y 4.
A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
const ll N = 10000;
const ll MOD = 1000000007;
 
ll F[N];
 
// Function to pre-compute the sequence
void precompute()
{
 
    // For N = 1 the answer will be 2
    F[1] = 2;
 
    // Starting two terms of the sequence
    F[2] = 3;
    F[3] = 4;
 
    // Compute the rest of the sequence
    // with the relation
    // F[i] = F[i - 1] + F[i - 2]
    for (int i = 4; i < N; i++)
        F[i] = (F[i - 1] + F[i - 2]) % MOD;
}
 
// Driver code
int main()
{
    int n = 8;
 
    // Pre-compute the sequence
    precompute();
 
    cout << F[n];
 
    return 0;
}

// Java implementation of the approach
class GFG
{
static int N = 10000;
static int MOD = 1000000007;
 
static int []F = new int[N];
 
// Function to pre-compute the sequence
static void precompute()
{
 
    // For N = 1 the answer will be 2
    F[1] = 2;
 
    // Starting two terms of the sequence
    F[2] = 3;
    F[3] = 4;
 
    // Compute the rest of the sequence
    // with the relation
    // F[i] = F[i - 1] + F[i - 2]
    for (int i = 4; i < N; i++)
        F[i] = (F[i - 1] + F[i - 2]) % MOD;
}
 
// Driver code
public static void main(String []args)
{
    int n = 8;
 
    // Pre-compute the sequence
    precompute();
 
    System.out.println(F[n]);
}
}
 
// This code is contributed by PrinciRaj1992

# Python implementation of the approach
N = 10000;
MOD = 1000000007;
 
F = [0] * N;
 
# Function to pre-compute the sequence
def precompute():
 
    # For N = 1 the answer will be 2
    F[1] = 2;
 
    # Starting two terms of the sequence
    F[2] = 3;
    F[3] = 4;
 
    # Compute the rest of the sequence
    # with the relation
    # F[i] = F[i - 1] + F[i - 2]
    for i in range(4,N):
        F[i] = (F[i - 1] + F[i - 2]) % MOD;
 
# Driver code
n = 8;
 
# Pre-compute the sequence
precompute();
print(F[n]);
 
# This code is contributed by 29AjayKumar

// C# implementation of the approach
using System;
     
class GFG
{
static int N = 10000;
static int MOD = 1000000007;
 
static int []F = new int[N];
 
// Function to pre-compute the sequence
static void precompute()
{
 
    // For N = 1 the answer will be 2
    F[1] = 2;
 
    // Starting two terms of the sequence
    F[2] = 3;
    F[3] = 4;
 
    // Compute the rest of the sequence
    // with the relation
    // F[i] = F[i - 1] + F[i - 2]
    for (int i = 4; i < N; i++)
        F[i] = (F[i - 1] + F[i - 2]) % MOD;
}
 
// Driver code
public static void Main(String []args)
{
    int n = 8;
 
    // Pre-compute the sequence
    precompute();
 
    Console.WriteLine(F[n]);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
var N = 10000;
var MOD = 1000000007;
 
var F = Array(N);
 
// Function to pre-compute the sequence
function precompute()
{
 
    // For N = 1 the answer will be 2
    F[1] = 2;
 
    // Starting two terms of the sequence
    F[2] = 3;
    F[3] = 4;
 
    // Compute the rest of the sequence
    // with the relation
    // F[i] = F[i - 1] + F[i - 2]
    for (var i = 4; i < N; i++)
        F[i] = (F[i - 1] + F[i - 2]) % MOD;
}
 
// Driver code
var n = 8;
// Pre-compute the sequence
precompute();
document.write( F[n]);
 
 
</script>

47

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N)