给定递推关系的第 N 项，其中每一项都等于前 K 项的乘积

---

递推关系 - 在数学中，递推关系是指一个方程，其中序列的第 n 项等于前几项的某种组合。

对于一个递推关系，其中每一项都等于前 K 项的乘积，让我们定义 N 和 K，以及一个包含关系前 K 项的数组 arr[]。

因此，第 n 项由下式给出：

$$\mathrm{F_N= F_{N−1} ∗ F_{N−2} ∗ F_{N−3} ∗ . . .∗ F_{N−K}}$$

问题陈述

给定两个正整数 N 和 K，以及一个包含 K 个正整数的整数数组。求递推关系的第 N 项。

示例 1

Input: N = 5, K = 3, arr[] = {2,1,4}
Output: 1024

解释

F0 = 2, F1 = 1, F2 = 4
F3 = 2*1*4 = 8
F4 = 1*4*8 = 32
F5 = 4*8*32 = 1024

示例 2

Input: N = 10, K = 4, arr[] = {0, 1, 3, 2}
Output: 0

解释

F0 = 0, F1 = 0, F2 = 0
F3 = 0, F4 = 0, F5 = 0, F6 = 0, F7 = 0, F8 = 0, F9 = 0, F10 = 0

方法 1：暴力求解

该问题的暴力求解方法是计算递推关系中的所有项，并打印所需的第 n 项。

伪代码

function NthTerm(arr[], K, N)
   Create an array ans of size N + 1 and initialize all elements to 0.
   // Initialize first K terms
   for i from 0 to K - 1
      ans[i] = F[i]
   // Find all terms from Kth term to the Nth term
   for i from K to N
      ans[i] = 1
      for j from i - K to i - 1
         // Current term is the product of previous K terms
         ans[i] = (ans[i] * ans[j]) % MOD  // If MOD is needed
   // Print the Nth term
   print ans[N]
end function

示例：C++ 实现

在下面的代码中，我们正在查找递推关系中的所有项。

#include <iostream>
#include <vector>

using namespace std;
const int MOD = 1000000007; // The modulus value if needed.
// Function to find the Nth term
void NthTerm(int arr[], int K, int N){
   // Stores the terms of recurrence relation
   vector<int> ans(N + 1, 0);
   // Initialize first K terms
   for (int i = 0; i < K; i++)
      ans[i] = arr[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 the product of previous K terms
         ans[i] = (1LL * ans[i] * ans[j]) % MOD;
      }
   }
   // Print the Nth term
   cout << ans[N] << endl;
}
int main(){
   // Given N, K, and F[]
   int arr[] = { 1, 2 };
   int K = 2;
   int N = 5;
   // Function Call
   NthTerm(arr, K, N);
   return 0;
}

输出

32

方法 2：优化方案

优化的解决方案将使用快速幂技术进行高效的模幂运算。可以使用双端队列数据结构来存储序列的项。

伪代码：

// Function to calculate (x ^ y) % p using fast exponentiation
function power(x, y, p):
   res = 1
   x = x % p
   while y > 0:
      if y is odd:
         res = (res * x) % p
      y = y >> 1
      x = (x * x) % p
   return res

// Function to calculate modular inverse using Fermat's Little Theorem
function modInverse(n, p):
   return power(n, p - 2, p)

// Function to find Nth term of the given recurrence relation
function NthTerm(arr[], K, N):
   Create an empty deque named q
   product = 1

   // Initialize the product of the first K terms and the deque
   for i from 0 to K - 1:
      product = (product * arr[i]) % MOD
      q.push_back(arr[i])

   // Push (K + 1)th term to the deque
   q.push_back(product)

   for i from K + 1 to N:
      f = q.front()
      e = q.back()

      // Calculate the (i + 1)th term
      next_term = ((e % MOD * e % MOD) % MOD * modInverse(f, MOD)) % MOD

      // Add the current term to the end of the deque
      q.push_back(next_term)

      // Remove the first number from the deque
      q.pop_front()

   // Print the Nth term
   print q.back()
end function

示例：C++ 实现

上述方法可以实现为。

#include <iostream>
#include <deque>

using namespace std;
const int MOD = 1000000007; // The modulus value if needed.
// Function to calculate (x ^ y) % p using fast exponentiation ( O(log y) )
int power(int x, int y, int p){
   int res = 1;
   x = x % p;
   while (y > 0) {
      if (y & 1)
         res = (res * x) % p;
      y = y >> 1;
      x = (x * x) % p;
   }
   return res;
}
// Function to find mod inverse using Fermat Little Theorem
int modInverse(int n, int p){
   return power(n, p - 2, p);
}
// Function to find the Nth term of the given recurrence relation
void NthTerm(int arr[], int K, int N){
   deque<int> q;
   int product = 1;
   // Initialize the product of the first K terms and the deque
   for (int i = 0; i < K; i++) {
      product = (product * arr[i]) % MOD;
      q.push_back(arr[i]);
   }
   // Push (K + 1)th term to the deque
   q.push_back(product);
   for (int i = K + 1; i <= N; i++) {
      int f = *q.begin();
      int e = *q.rbegin();
      // Calculate the ith term
      int next_term = ((e % MOD * e % MOD) % MOD * (modInverse(f, MOD))) % MOD;
      // Add the current term to the end of the deque
      q.push_back(next_term);
      // Remove the first number from the deque
      q.pop_front();
   }
   // Print the Nth term
   cout << *q.rbegin() << endl;
}
int main(){
   // Given N, K, and arr[]
   int arr[] = { 1, 2 };
   int K = 2;
   int N = 5;
   // Function Call
   NthTerm(arr, K, N);
   return 0;
}

输出

0

结论

总而言之，可以使用上述两种方法找到给定递推关系的第 N 项，其中每一项都等于前 K 项的乘积，第一种方法是暴力求解方法，然后是更优化的方案。