Dado un número entero N y dos arrays F[] y C[] de tamaño K que representan los primeros K términos y el coeficiente de los primeros K términos de la siguiente relación de recurrencia, respectivamente.
F norte = C 1 *F norte – 1 + C 2 *F norte – 2 + C 3 *F norte – 3 +….+ C K *F norte – K .
La tarea es encontrar el término N de la relación de recurrencia. Dado que el número puede ser muy grande, tome el módulo a 10 9 + 7 .
Ejemplos:
Entrada: N = 10, K = 2, F[] = {0, 1}, C[] = {1, 1}
Salida: 55
Explicación:
F N = F N – 1 + F N – 2 con F 0 = 0, F 1 = 1
La relación de recurrencia anterior forma la secuencia de Fibonacci con dos valores iniciales.
Los términos restantes de la serie se pueden calcular como la suma de los K términos anteriores con la multiplicación correspondiente con el coeficiente almacenado en C[] .
Por lo tanto, F 10 = 55.Entrada: N = 5, K = 3, F[] = {1, 2, 3}, C[] = {1, 1, 1}
Salida: 20
Explicación:
La secuencia de la relación de recurrencia anterior es 1, 2, 3, 6, 11, 20, 37, 68, ….
Cada término siguiente es la suma de los términos anteriores (K = 3) con la condición base F 0 = 1, F 1 = 2 y F 2 = 3
Por lo tanto, F 5 = 20.
Enfoque ingenuo: la idea es generar la secuencia usando la relación de recurrencia dada calculando cada término con la ayuda de los K términos anteriores. Imprime el término N después de formar la secuencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
// Function to calculate Nth term of
// general recurrence relations
void NthTerm(int F[], int C[], int K,
int n)
{
// Stores the generated sequence
int ans[n + 1] = { 0 };
for (int i = 0; i < K; i++)
ans[i] = F[i];
for (int i = K; i <= n; i++) {
for (int j = i - K; j < i; j++) {
// Current term is sum of
// previous k terms
ans[i] += ans[j];
ans[i] %= mod;
}
}
// Print the nth term
cout << ans[n] << endl;
}
// Driver Code
int main()
{
// Given Array F[] and C[]
int F[] = { 0, 1 };
int C[] = { 1, 1 };
// Given N and K
int K = 2;
int N = 10;
// Function Call
NthTerm(F, C, K, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG{
static double mod = 1e9 + 7;
// Function to calculate Nth term of
// general recurrence relations
static void NthTerm(int F[], int C[], int K,
int n)
{
// Stores the generated sequence
int ans[] = new int[n + 1 ];
for(int i = 0; i < K; i++)
ans[i] = F[i];
for(int i = K; i <= n; i++)
{
for(int j = i - K; j < i; j++)
{
// Current term is sum of
// previous k terms
ans[i] += ans[j];
ans[i] %= mod;
}
}
// Print the nth term
System.out.println(ans[n]);
}
// Driver Code
public static void main (String[] args)
{
// Given Array F[] and C[]
int F[] = { 0, 1 };
int C[] = { 1, 1 };
// Given N and K
int K = 2;
int N = 10;
// Function call
NthTerm(F, C, K, N);
}
}
// This code is contributed by jana_sayantan
Python3
# Python3 program for the above approach mod = 1e9 + 7 # Function to calculate Nth term of # general recurrence relations def NthTerm(F, C, K, n): # Stores the generated sequence ans = [0] * (n + 1) i = 0 while i < K: ans[i] = F[i] i += 1 i = K while i <= n: j = i - K while j < i: # Current term is sum of # previous k terms ans[i] += ans[j] ans[i] %= mod j += 1 i += 1 # Print the nth term print(int(ans[n])) # Driver code if __name__ == '__main__': # Given Array F[] and C[] F = [ 0, 1 ] C = [ 1, 1 ] # Given N and K K = 2 N = 10 # Function call NthTerm(F, C, K, N) # This code is contributed by jana_sayantan
C#
// C# program for
// the above approach
using System;
class GFG{
static double mod = 1e9 + 7;
// Function to calculate Nth term of
// general recurrence relations
static void NthTerm(int [] F, int [] C,
int K, int n)
{
// Stores the generated sequence
int []ans = new int[n + 1];
for(int i = 0; i < K; i++)
ans[i] = F[i];
for(int i = K; i <= n; i++)
{
for(int j = i - K; j < i; j++)
{
// Current term is sum of
// previous k terms
ans[i] += ans[j];
ans[i] %= (int)mod;
}
}
// Print the nth term
Console.WriteLine(ans[n]);
}
// Driver Code
public static void Main (String[] args)
{
// Given Array F[] and C[]
int [] F= {0, 1};
int [] C= {1, 1};
// Given N and K
int K = 2;
int N = 10;
// Function call
NthTerm(F, C, K, N);
}
}
// This code is contributed by jana_sayantan
Javascript
<script>
// JavaScript program for the above approach
let mod = 1e9 + 7;
// Function to calculate Nth term of
// general recurrence relations
function NthTerm(F, C, K, n)
{
// Stores the generated sequence
let ans = new Uint8Array(n + 1);
for (let i = 0; i < K; i++)
ans[i] = F[i];
for (let i = K; i <= n; i++) {
for (let j = i - K; j < i; j++) {
// Current term is sum of
// previous k terms
ans[i] += ans[j];
ans[i] %= mod;
}
}
// Print the nth term
document.write(ans[n] + "<br>");
}
// Driver Code
// Given Array F[] and C[]
let F = [ 0, 1 ];
let C = [ 1, 1 ];
// Given N and K
let K = 2;
let N = 10;
// Function Call
NthTerm(F, C, K, N);
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
55
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: El término N de la relación de recurrencia se puede encontrar utilizando Exponenciación matricial . A continuación se muestran los pasos:
- Consideremos los estados iniciales como:
F = [f 0 , f 1 , f 2 …………………………………f k-1 ]
- Defina una array de tamaño K 2 como:
T =
- Calcule la potencia N-ésima de la array T[][] usando exponenciación binaria .
- Ahora, multiplicando F[] con la potencia N de T[][] da:
FxT N = [F N , F N + 1 , F N + 2 , …………………….., F N + K ]
- El primer término de la array resultante F x T N es el resultado requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
// Declare T[][] as global matrix
int T[2000][2000];
// Result matrix
int result[2000][2000];
// Function to multiply two matrices
void mul_2(int K)
{
// Create an auxiliary matrix to
// store elements of the
// multiplication matrix
int temp[K + 1][K + 1];
memset(temp, 0, sizeof temp);
// Iterate over range [0, K]
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= K; j++) {
for (int k = 1; k <= K; k++) {
// Update temp[i][j]
temp[i][j]
= (temp[i][j]
+ (T[i][k] * T[k][j])
% mod)
% mod;
}
}
}
// Update the final matrix
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= K; j++) {
T[i][j] = temp[i][j];
}
}
}
// Function to multiply two matrices
void mul_1(int K)
{
// Create an auxiliary matrix to
// store elements of the
// multiplication matrix
int temp[K + 1][K + 1];
memset(temp, 0, sizeof temp);
// Iterate over range [0, K]
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= K; j++) {
for (int k = 1; k <= K; k++) {
// Update temp[i][j]
temp[i][j]
= (temp[i][j]
+ (result[i][k] * T[k][j])
% mod)
% mod;
}
}
}
// Update the final matrix
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= K; j++) {
result[i][j] = temp[i][j];
}
}
}
// Function to calculate matrix^n
// using binary exponentaion
void matrix_pow(int K, int n)
{
// Initialize result matrix
// and unity matrix
for (int i = 1; i <= K; i++) {
for (int j = 1; j <= K; j++) {
if (i == j)
result[i][j] = 1;
}
}
while (n > 0) {
if (n % 2 == 1)
mul_1(K);
mul_2(K);
n /= 2;
}
}
// Function to calculate nth term
// of general recurrence
int NthTerm(int F[], int C[], int K,
int n)
{
// Fill T[][] with appropriate value
for (int i = 1; i <= K; i++)
T[i][K] = C[K - i];
for (int i = 1; i <= K; i++)
T[i + 1][i] = 1;
// Function Call to calculate T^n
matrix_pow(K, n);
int answer = 0;
// Calculate nth term as first
// element of F*(T^n)
for (int i = 1; i <= K; i++) {
answer += F[i - 1] * result[i][1];
}
// Print the result
cout << answer << endl;
return 0;
}
// Driver Code
int main()
{
// Given Initial terms
int F[] = { 1, 2, 3 };
// Given coefficients
int C[] = { 1, 1, 1 };
// Given K
int K = 3;
// Given N
int N = 10;
// Function Call
NthTerm(F, C, K, N);
return 0;
}
Java
// Java program for
// the above approach
import java.util.*;
class GFG{
static int mod = (int) (1e9 + 7);
// Declare T[][] as global matrix
static int [][]T = new int[2000][2000];
// Result matrix
static int [][]result = new int[2000][2000];
// Function to multiply two matrices
static void mul_2(int K)
{
// Create an auxiliary matrix to
// store elements of the
// multiplication matrix
int [][]temp = new int[K + 1][K + 1];
// Iterate over range [0, K]
for (int i = 1; i <= K; i++)
{
for (int j = 1; j <= K; j++)
{
for (int k = 1; k <= K; k++)
{
// Update temp[i][j]
temp[i][j] = (temp[i][j] +
(T[i][k] * T[k][j]) %
mod) % mod;
}
}
}
// Update the final matrix
for (int i = 1; i <= K; i++)
{
for (int j = 1; j <= K; j++)
{
T[i][j] = temp[i][j];
}
}
}
// Function to multiply two matrices
static void mul_1(int K)
{
// Create an auxiliary matrix to
// store elements of the
// multiplication matrix
int [][]temp = new int[K + 1][K + 1];
// Iterate over range [0, K]
for (int i = 1; i <= K; i++)
{
for (int j = 1; j <= K; j++)
{
for (int k = 1; k <= K; k++)
{
// Update temp[i][j]
temp[i][j] = (temp[i][j] +
(result[i][k] * T[k][j]) %
mod) % mod;
}
}
}
// Update the final matrix
for (int i = 1; i <= K; i++)
{
for (int j = 1; j <= K; j++)
{
result[i][j] = temp[i][j];
}
}
}
// Function to calculate matrix^n
// using binary exponentaion
static void matrix_pow(int K, int n)
{
// Initialize result matrix
// and unity matrix
for (int i = 1; i <= K; i++)
{
for (int j = 1; j <= K; j++)
{
if (i == j)
result[i][j] = 1;
}
}
while (n > 0)
{
if (n % 2 == 1)
mul_1(K);
mul_2(K);
n /= 2;
}
}
// Function to calculate nth term
// of general recurrence
static int NthTerm(int F[], int C[],
int K, int n)
{
// Fill T[][] with appropriate value
for (int i = 1; i <= K; i++)
T[i][K] = C[K - i];
for (int i = 1; i <= K; i++)
T[i + 1][i] = 1;
// Function Call to calculate T^n
matrix_pow(K, n);
int answer = 0;
// Calculate nth term as first
// element of F * (T ^ n)
for (int i = 1; i <= K; i++)
{
answer += F[i - 1] * result[i][1];
}
// Print the result
System.out.print(answer + "\n");
return 0;
}
// Driver Code
public static void main(String[] args)
{
// Given Initial terms
int F[] = {1, 2, 3};
// Given coefficients
int C[] = {1, 1, 1};
// Given K
int K = 3;
// Given N
int N = 10;
// Function Call
NthTerm(F, C, K, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for # the above approach mod = 1e9 + 7 # Declare T[][] as global matrix T = [[0 for x in range (2000)] for y in range (2000)] # Result matrix result = [[0 for x in range (2000)] for y in range (2000)] # Function to multiply two matrices def mul_2(K): # Create an auxiliary matrix to # store elements of the # multiplication matrix temp = [[0 for x in range (K + 1)] for y in range (K + 1)] # Iterate over range [0, K] for i in range (1, K + 1): for j in range (1, K + 1): for k in range (1, K + 1): # Update temp[i][j] temp[i][j] = ((temp[i][j] + (T[i][k] * T[k][j]) % mod) % mod) # Update the final matrix for i in range (1, K + 1): for j in range (1, K + 1): T[i][j] = temp[i][j] # Function to multiply two matrices def mul_1(K): # Create an auxiliary matrix to # store elements of the # multiplication matrix temp = [[0 for x in range (K + 1)] for y in range (K + 1)] # Iterate over range [0, K] for i in range (1, K + 1): for j in range (1, K + 1): for k in range (1, K + 1): # Update temp[i][j] temp[i][j] = ((temp[i][j] + (result[i][k] * T[k][j]) % mod) % mod) # Update the final matrix for i in range (1, K + 1): for j in range (1, K + 1): result[i][j] = temp[i][j] # Function to calculate matrix^n # using binary exponentaion def matrix_pow(K, n): # Initialize result matrix # and unity matrix for i in range (1, K + 1): for j in range (1, K + 1): if (i == j): result[i][j] = 1 while (n > 0): if (n % 2 == 1): mul_1(K) mul_2(K) n //= 2 # Function to calculate nth term # of general recurrence def NthTerm(F, C, K, n): # Fill T[][] with appropriate value for i in range (1, K + 1): T[i][K] = C[K - i] for i in range (1, K + 1): T[i + 1][i] = 1 # Function Call to calculate T^n matrix_pow(K, n) answer = 0 # Calculate nth term as first # element of F*(T^n) for i in range (1, K + 1): answer += F[i - 1] * result[i][1] # Print the result print(int(answer)) # Driver Code if __name__ == "__main__": # Given Initial terms F = [1, 2, 3] # Given coefficients C = [1, 1, 1] # Given K K = 3 # Given N N = 10 # Function Call NthTerm(F, C, K, N) # This code is contributed by Chitranayal
C#
// C# program for
// the above approach
using System;
class GFG{
static int mod = (int) (1e9 + 7);
// Declare T[,] as global matrix
static int [,]T = new int[2000, 2000];
// Result matrix
static int [,]result = new int[2000, 2000];
// Function to multiply two matrices
static void mul_2(int K)
{
// Create an auxiliary matrix to
// store elements of the
// multiplication matrix
int [,]temp = new int[K + 1,
K + 1];
// Iterate over range [0, K]
for (int i = 1; i <= K; i++)
{
for (int j = 1; j <= K; j++)
{
for (int k = 1; k <= K; k++)
{
// Update temp[i,j]
temp[i, j] = (temp[i, j] +
(T[i, k] * T[k, j]) %
mod) % mod;
}
}
}
// Update the readonly matrix
for (int i = 1; i <= K; i++)
{
for (int j = 1; j <= K; j++)
{
T[i, j] = temp[i, j];
}
}
}
// Function to multiply two matrices
static void mul_1(int K)
{
// Create an auxiliary matrix to
// store elements of the
// multiplication matrix
int [,]temp = new int[K + 1,
K + 1];
// Iterate over range [0, K]
for (int i = 1; i <= K; i++)
{
for (int j = 1; j <= K; j++)
{
for (int k = 1; k <= K; k++)
{
// Update temp[i,j]
temp[i,j] = (temp[i, j] +
(result[i, k] * T[k, j]) %
mod) % mod;
}
}
}
// Update the readonly matrix
for (int i = 1; i <= K; i++)
{
for (int j = 1; j <= K; j++)
{
result[i, j] = temp[i, j];
}
}
}
// Function to calculate matrix^n
// using binary exponentaion
static void matrix_pow(int K, int n)
{
// Initialize result matrix
// and unity matrix
for (int i = 1; i <= K; i++)
{
for (int j = 1; j <= K; j++)
{
if (i == j)
result[i, j] = 1;
}
}
while (n > 0)
{
if (n % 2 == 1)
mul_1(K);
mul_2(K);
n /= 2;
}
}
// Function to calculate nth term
// of general recurrence
static int NthTerm(int []F, int []C,
int K, int n)
{
// Fill T[,] with appropriate value
for (int i = 1; i <= K; i++)
T[i, K] = C[K - i];
for (int i = 1; i <= K; i++)
T[i + 1, i] = 1;
// Function Call to calculate T^n
matrix_pow(K, n);
int answer = 0;
// Calculate nth term as first
// element of F * (T ^ n)
for (int i = 1; i <= K; i++)
{
answer += F[i - 1] * result[i, 1];
}
// Print the result
Console.Write(answer + "\n");
return 0;
}
// Driver Code
public static void Main(String[] args)
{
// Given Initial terms
int []F = {1, 2, 3};
// Given coefficients
int []C = {1, 1, 1};
// Given K
int K = 3;
// Given N
int N = 10;
// Function Call
NthTerm(F, C, K, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
let mod = (1e9 + 7);
// Declare T[][] as global matrix
let T = new Array(2000);
// Result matrix
let result = new Array(2000);
for (let i = 0; i < 2000; i++)
{
T[i] = new Array(2000);
result[i] = new Array(2000);
for (let j = 0; j < 2000; j++)
{
T[i][j] = 0;
result[i][j] = 0;
}
}
// Function to multiply two matrices
function mul_2(K)
{
// Create an auxiliary matrix to
// store elements of the
// multiplication matrix
let temp = new Array(K + 1);
for (let i = 0; i <= K; i++)
{
temp[i] = new Array(K + 1);
for (let j = 0; j <= K; j++)
{
temp[i][j] = 0;
}
}
// Iterate over range [0, K]
for (let i = 1; i <= K; i++)
{
for (let j = 1; j <= K; j++)
{
for (let k = 1; k <= K; k++)
{
// Update temp[i][j]
temp[i][j] = (temp[i][j] +
(T[i][k] * T[k][j]) %
mod) % mod;
}
}
}
// Update the final matrix
for (let i = 1; i <= K; i++)
{
for (let j = 1; j <= K; j++)
{
T[i][j] = temp[i][j];
}
}
}
// Function to multiply two matrices
function mul_1(K)
{
// Create an auxiliary matrix to
// store elements of the
// multiplication matrix
let temp = new Array(K + 1);
for (let i = 0; i <= K; i++)
{
temp[i] = new Array(K + 1);
for (let j = 0; j <= K; j++)
{
temp[i][j] = 0;
}
}
// Iterate over range [0, K]
for (let i = 1; i <= K; i++)
{
for (let j = 1; j <= K; j++)
{
for (let k = 1; k <= K; k++)
{
// Update temp[i][j]
temp[i][j] = (temp[i][j] +
(result[i][k] * T[k][j]) %
mod) % mod;
}
}
}
// Update the final matrix
for (let i = 1; i <= K; i++)
{
for (let j = 1; j <= K; j++)
{
result[i][j] = temp[i][j];
}
}
}
// Function to calculate matrix^n
// using binary exponentaion
function matrix_pow(K, n)
{
// Initialize result matrix
// and unity matrix
for (let i = 1; i <= K; i++)
{
for (let j = 1; j <= K; j++)
{
if (i == j)
result[i][j] = 1;
}
}
while (n > 0)
{
if (n % 2 == 1)
mul_1(K);
mul_2(K);
n = parseInt(n / 2, 10);
}
}
// Function to calculate nth term
// of general recurrence
function NthTerm(F, C, K, n)
{
// Fill T[][] with appropriate value
for (let i = 1; i <= K; i++)
T[i][K] = C[K - i];
for (let i = 1; i <= K; i++)
T[i + 1][i] = 1;
// Function Call to calculate T^n
matrix_pow(K, n);
let answer = 0;
// Calculate nth term as first
// element of F * (T ^ n)
for (let i = 1; i <= K; i++)
{
answer += F[i - 1] * result[i][1];
}
// Print the result
document.write(answer + "</br>");
return 0;
}
// Given Initial terms
let F = [1, 2, 3];
// Given coefficients
let C = [1, 1, 1];
// Given K
let K = 3;
// Given N
let N = 10;
// Function Call
NthTerm(F, C, K, N);
// This code is contributed by mukesh07.
</script>
Producción:
423
Complejidad de tiempo: O(K 3 log(N))
Espacio auxiliar: O(K*K)
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