給定遞推關係的第 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 項的乘積，第一種方法是暴力求解方法，然後是更最佳化的方案。