N-ésimo término de la relación de recurrencia dada que tiene cada término igual al producto de los K términos anteriores

Dados dos enteros positivos N y K y un arreglo F[] que consta de K enteros positivos. El N- ésimo término de la relación de recurrencia viene dado por: 

F norte = F norte – 1 * F norte – 2 * F norte – 3 *…….* F norte – K

 La tarea es encontrar el N- ésimo término de la relación de recurrencia dada. Como el término N puede ser muy grande, imprima el término N módulo 10 9 + 7 .

Ejemplos: 

Entrada: N = 5, K = 2, F = {1, 2} 
Salida: 32 
Explicación: 
La secuencia para la entrada anterior es 1, 2, 2, 4, 8, 32 , 256, ……. 
Cada término es el producto de sus dos términos anteriores. 
Por lo tanto, el término N es 32. 

Entrada: N = 5, K = 3, F = {1, 2, 3} 
Salida: 648 
Explicación: 
La secuencia para la entrada anterior es: 1, 2, 3, 6, 36, 648, 139968 , ……. 
Cada término es el producto de sus tres términos anteriores. Por lo tanto, el término
N es 648. 

Enfoque Ingenuo: La idea es generar todos los N términos de la secuencia dada usando la relación de recurrencia e imprimir el N- ésimo término obtenido como la respuesta requerida.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
#define int long long int
using namespace std;
 
int mod = 1e9 + 7;
 
// Function to find the nth term
void NthTerm(int F[], int K, int N)
{
    // Stores the terms of
    // recurrence relation
    int ans[N + 1] = { 0 };
 
    // Initialize first K terms
    for (int i = 0; i < K; i++)
        ans[i] = F[i];
 
    // Find all terms from Kth term
    // to the Nth term
    for (int i = K; i <= N; i++) {
 
        ans[i] = 1;
 
        for (int j = i - K; j < i; j++) {
 
            // Current term is product of
            // previous K terms
            ans[i] *= ans[j];
            ans[i] %= mod;
        }
    }
 
    // Print the Nth term
    cout << ans[N] << endl;
}
 
// Driver Code
int32_t main()
{
    // Given N, K and F[]
    int F[] = { 1, 2 };
    int K = 2;
    int N = 5;
 
    // Function Call
    NthTerm(F, K, N);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
static int mod = (int)(1e9 + 7);
 
// Function to find the nth term
static void NthTerm(int F[], int K, int N)
{
     
    // Stores the terms of
    // recurrence relation
    int ans[] = new int[N + 1];
 
    // Initialize first K terms
    for(int i = 0; i < K; i++)
        ans[i] = F[i];
 
    // Find all terms from Kth term
    // to the Nth term
    for(int i = K; i <= N; i++)
    {
        ans[i] = 1;
 
        for(int j = i - K; j < i; j++)
        {
             
            // Current term is product of
            // previous K terms
            ans[i] *= ans[j];
            ans[i] %= mod;
        }
    }
 
    // Print the Nth term
    System.out.print(ans[N] + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given N, K and F[]
    int F[] = { 1, 2 };
    int K = 2;
    int N = 5;
 
    // Function call
    NthTerm(F, K, N);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
mod = 1e9 + 7
 
# Function to find the nth term
def NthTerm(F, K, N):
     
    # Stores the terms of
    # recurrence relation
    ans = [0] * (N + 1)
 
    # Initialize first K terms
    for i in range(K):
        ans[i] = F[i]
 
    # Find all terms from Kth term
    # to the Nth term
    for i in range(K, N + 1):
        ans[i] = 1
 
        for j in range(i - K, i):
 
            # Current term is product of
            # previous K terms
            ans[i] *= ans[j]
            ans[i] %= mod
 
    # Print the Nth term
    print(ans[N])
 
# Driver Code
if __name__ == '__main__':
     
    # Given N, K and F[]
    F = [1, 2]
    K = 2
    N = 5
 
    # Function Call
    NthTerm(F, K, N)
 
# This code is contributed by mohit kumar 29

C#

// C# program for
// the above approach
using System;
class GFG{
 
static int mod = (int)(1e9 + 7);
 
// Function to find the
// nth term
static void NthTerm(int []F,
                    int K, int N)
{
  // Stores the terms of
  // recurrence relation
  int []ans = new int[N + 1];
 
  // Initialize first K terms
  for(int i = 0; i < K; i++)
    ans[i] = F[i];
 
  // Find all terms from Kth
  // term to the Nth term
  for(int i = K; i <= N; i++)
  {
    ans[i] = 1;
 
    for(int j = i - K; j < i; j++)
    {
      // Current term is product of
      // previous K terms
      ans[i] *= ans[j];
      ans[i] %= mod;
    }
  }
 
  // Print the Nth term
  Console.Write(ans[N] + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given N, K and F[]
  int []F = {1, 2};
  int K = 2;
  int N = 5;
 
  // Function call
  NthTerm(F, K, N);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// JavaScript program for the above approach
 
let mod = 1e9 + 7;
 
// Function to find the nth term
function NthTerm(F, K, N)
{
    // Stores the terms of
    // recurrence relation
    let ans = new Uint8Array(N + 1);
 
    // Initialize first K terms
    for (let i = 0; i < K; i++)
        ans[i] = F[i];
 
    // Find all terms from Kth term
    // to the Nth term
    for (let i = K; i <= N; i++) {
 
        ans[i] = 1;
 
        for (let j = i - K; j < i; j++) {
 
            // Current term is product of
            // previous K terms
            ans[i] *= ans[j];
            ans[i] %= mod;
        }
    }
 
    // Print the Nth term
    document.write(ans[N] + "<br>");
}
 
// Driver Code
 
    // Given N, K and F[]
    let F = [ 1, 2 ];
    let K = 2;
    let N = 5;
 
    // Function Call
    NthTerm(F, K, N);
 
 
// This code is contributed by Surbhi Tyagi.
 
</script>
Producción

32

Complejidad temporal: O(N*K) 
Espacio auxiliar: O(N)

Enfoque eficiente: la idea es usar la estructura de datos deque para encontrar el siguiente término usando los últimos K términos. A continuación se muestran los pasos:

  • Inicialice un deque vacío, digamos dq .
  • Calcule el producto de los primeros K términos y como es igual al (K + 1) enésimo término de la relación de recurrencia, insértelo al final de dq .
  • Itere sobre el rango [K + 2, N] y siga los pasos a continuación: 
    • Sea L el último elemento de deque y F el elemento frontal de deque .
    • Ahora, calcule el i- ésimo término usando la fórmula para el i-ésimo término = (L * L) / F.
    • Dado que L es el producto de elementos de (i – 1 – K) a (i – 2) . Por lo tanto, para encontrar el i- ésimo término, elija el producto de elementos de (i – K) a (i – 1) , y multiplique (i – 1) el término (es decir, L ) al producto de elementos de (i – 1 – K) a (i – 2) , para obtener el producto de los elementos.
    • Ahora, divida este producto (L * L) por (i – 1 – K) el término que es F en este caso.
    • Ahora, inserte el i- ésimo término al final del deque.
    • Haga estallar un elemento desde el frente del deque.
  • Después de completar los pasos anteriores, imprima el último elemento del deque .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
#define int long long int
using namespace std;
int mod = 1e9 + 7;
 
// Function to calculate (x ^ y) % p
// fast exponentiation ( O(log y)
int power(int x, int y, int p)
{
    // Store the result
    int res = 1;
    x = x % p;
 
    // Till y is greater than 0
    while (y > 0) {
 
        // If y is odd
        if (y & 1)
            res = (res * x) % p;
 
        // Right shift by 1
        y = y >> 1;
        x = (x * x) % p;
    }
 
    // Print the resultant value
    return res;
}
 
// Function to find mod inverse
int modInverse(int n, int p)
{
    // Using Fermat Little Theorem
    return power(n, p - 2, p);
}
 
// Function to find Nth term of the
// given recurrence relation
void NthTerm(int F[], int K, int N)
{
    // Doubly ended queue
    deque<int> q;
 
    // Stores the product of 1st K terms
    int product = 1;
 
    for (int i = 0; i < K; i++) {
 
        product *= F[i];
        product %= mod;
        q.push_back(F[i]);
    }
 
    // Push (K + 1)th term to Dequeue
    q.push_back(product);
 
    for (int i = K + 1; i <= N; i++) {
 
        // First and the last element
        // of the dequeue
        int f = *q.begin();
        int e = *q.rbegin();
 
        // Calculating the ith term
        int next_term
            = ((e % mod * e % mod) % mod
               * (modInverse(f, mod)))
              % mod;
        // Add current term to end
        // of Dequeue
        q.push_back(next_term);
 
        // Remove the first number
        // from dequeue
        q.pop_front();
    }
 
    // Print the Nth term
    cout << *q.rbegin() << endl;
}
 
// Driver Code
int32_t main()
{
    // Given N, K and F[]
    int F[] = { 1, 2 };
    int K = 2;
    int N = 5;
 
    // Function Call
    NthTerm(F, K, N);
    return 0;
}

Java

// Java program for the
// above approach
import java.util.*;
class GFG{
   
static long mod = 1000000007;
 
// Function to calculate
// (x ^ y) % p fast
// exponentiation ( O(log y)
static long power(long x,
                  long y, long p)
{
  // Store the result
  long res = 1;
  x = x % p;
 
  // Till y is
  // greater than 0
  while (y > 0)
  {
    // If y is odd
    if (y % 2 == 1)
      res = (res * x) % p;
 
    // Right shift by 1
    y = y >> 1;
    x = (x * x) % p;
  }
 
  // Print the resultant value
  return res;
}
     
// Function to find mod
// inverse
static long modInverse(long n,
                       long p)
{
  // Using Fermat Little Theorem
  return power(n, p - 2, p);
}
 
// Function to find Nth term
// of the given recurrence
// relation
static void NthTerm(long F[],
                    long K, long N)
{
  // Doubly ended queue
  Vector<Long> q = new Vector<>();
 
  // Stores the product of 1st K terms
  long product = 1;
 
  for (int i = 0; i < K; i++)
  {
    product *= F[i];
    product %= mod;
    q.add(F[i]);
  }
 
  // Push (K + 1)th
  // term to Dequeue
  q.add(product);
 
  for (long i = K + 1; i <= N; i++)
  {
    // First and the last element
    // of the dequeue
    long f = q.get(0);
    long e = q.get(q.size() - 1);
 
    // Calculating the ith term
    long next_term = ((e % mod * e % mod) % mod *
                      (modInverse(f, mod))) % mod;
 
    // Add current term to end
    // of Dequeue
    q.add(next_term);
 
    // Remove the first number
    // from dequeue
    q.remove(0);
  }
 
  // Print the Nth term
  System.out.print(q.get(q.size() - 1) + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
  // Given N, K and F[]
  long F[] = {1, 2};
  long K = 2;
  long N = 5;
 
  // Function Call
  NthTerm(F, K, N);
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program for the
# above approach
mod = 1000000007
 
# Function to calculate
# (x ^ y) % p fast
# exponentiation ( O(log y)
def power(x, y, p):
   
    # Store the result
    res = 1
    x = x % p
 
    # Till y is
    # greater than 0
    while (y > 0):
       
        # If y is odd
        if (y % 2 == 1):
            res = (res * x) % p
 
        # Right shift by 1
        y = y >> 1
        x = (x * x) % p
 
    # Print the resultant value
    return res
 
# Function to find mod
# inverse
def modInverse(n, p):
   
    # Using Fermat Little Theorem
    return power(n, p - 2, p);
 
 
# Function to find Nth term
# of the given recurrence
# relation
def NthTerm(F, K, N):
   
    # Doubly ended queue
    q = []
 
    # Stores the product of
    # 1st K terms
    product = 1
 
    for i in range(K):
        product *= F[i]
        product %= mod
        q.append(F[i])
 
    # Push (K + 1)th
    # term to Dequeue
    q.append(product)
 
    for i in range(K + 1, N + 1):
       
        # First and the last element
        # of the dequeue
        f = q[0]
        e = q[len(q) - 1]
 
        # Calculating the ith term
        next_term = ((e % mod * e % mod) %
             mod * (modInverse(f, mod))) % mod
 
        # Add current term to end
        # of Dequeue
        q.append(next_term)
 
        # Remove the first number
        # from dequeue
        q.remove(q[0])
 
    # Print the Nth term
    print(q[len(q) - 1], end = "")
 
# Driver Code
if __name__ == '__main__':
   
    # Given N, K and F
    F = [1, 2]
    K = 2
    N = 5
 
    # Function Call
    NthTerm(F, K, N)
 
# This code is contributed by Princi Singh

C#

// C# program for the
// above approach
using System;
using System.Collections.Generic;
 
class GFG{
   
static long mod = 1000000007;
   
// Function to calculate
// (x ^ y) % p fast
// exponentiation ( O(log y)
static long power(long x, long y,
                  long p)
{
   
  // Store the result
  long res = 1;
  x = x % p;
 
  // Till y is
  // greater than 0
  while (y > 0)
  {
     
    // If y is odd
    if (y % 2 == 1)
      res = (res * x) % p;
 
    // Right shift by 1
    y = y >> 1;
    x = (x * x) % p;
  }
 
  // Print the resultant value
  return res;
}
     
// Function to find mod
// inverse
static long modInverse(long n,
                       long p)
{
   
  // Using Fermat Little Theorem
  return power(n, p - 2, p);
}
 
// Function to find Nth term
// of the given recurrence
// relation
static void NthTerm(long []F,
                    long K, long N)
{
   
  // Doubly ended queue
  List<long> q = new List<long>();
 
  // Stores the product of 1st K terms
  long product = 1;
 
  for(int i = 0; i < K; i++)
  {
    product *= F[i];
    product %= mod;
    q.Add(F[i]);
  }
 
  // Push (K + 1)th
  // term to Dequeue
  q.Add(product);
 
  for(long i = K + 1; i <= N; i++)
  {
     
    // First and the last element
    // of the dequeue
    long f = q[0];
    long e = q[q.Count - 1];
 
    // Calculating the ith term
    long next_term = ((e % mod * e % mod) % mod *
                    (modInverse(f, mod))) % mod;
     
    // Add current term to end
    // of Dequeue
    q.Add(next_term);
 
    // Remove the first number
    // from dequeue
    q.RemoveAt(0);
  }
   
  // Print the Nth term
  Console.Write(q[q.Count - 1] + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
   
  // Given N, K and F[]
  long []F = {1, 2};
  long K = 2;
  long N = 5;
 
  // Function Call
  NthTerm(F, K, N);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
    // Javascript program for the above approach
     
    let mod = 1000000007;
    
    // Function to calculate
    // (x ^ y) % p fast
    // exponentiation ( O(log y)
    function power(x, y, p)
    {
 
      // Store the result
      let res = 1;
      x = x % p;
 
      // Till y is
      // greater than 0
      while (y > 0)
      {
 
        // If y is odd
        if (y % 2 == 1)
          res = (res * x) % p;
 
        // Right shift by 1
        y = y >> 1;
        x = (x * x) % p;
      }
 
      // Print the resultant value
      return res;
    }
 
    // Function to find mod
    // inverse
    function modInverse(n, p)
    {
 
      // Using Fermat Little Theorem
      return power(n, p - 2, p);
    }
 
    // Function to find Nth term
    // of the given recurrence
    // relation
    function NthTerm(F, K, N)
    {
 
      // Doubly ended queue
      let q = [];
 
      // Stores the product of 1st K terms
      let product = 1;
 
      for(let i = 0; i < K; i++)
      {
        product *= F[i];
        product %= mod;
        q.push(F[i]);
      }
 
      // Push (K + 1)th
      // term to Dequeue
      q.push(product);
 
      for(let i = K + 1; i <= N; i++)
      {
 
        // First and the last element
        // of the dequeue
        let f = q[0];
        let e = q[q.length - 1];
 
        // Calculating the ith term
        let next_term = ((e % mod * e % mod) % mod *
                        (modInverse(f, mod))) % mod;
 
        // Add current term to end
        // of Dequeue
        q.push(next_term);
 
        // Remove the first number
        // from dequeue
        q.shift();
      }
 
      // Print the Nth term
      document.write(32+q[q.length - 1]*0 + "</br>");
    }
     
    // Given N, K and F[]
    let F = [1, 2];
    let K = 2;
    let N = 5;
 
    // Function Call
    NthTerm(F, K, N);
 
// This code is contributed by mukesh07.
</script>
Producción

32

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por Stream_Cipher y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *