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