곱이 <=K인 모든 하위 시퀀스 계산 – C++의 재귀 접근 방식

이 튜토리얼에서는 제품이 <=k인 부분 시퀀스의 수를 찾는 프로그램에 대해 논의할 것입니다.

이를 위해 배열과 값 K가 제공됩니다. 우리의 임무는 곱이 K인 부분 시퀀스의 수를 찾는 것입니다.

예시

#include <bits/stdc++.h>
#define ll long long
using namespace std;
//keeping count of discarded sub sequences
ll discard_count = 0;
ll power(ll a, ll n){
   if (n == 0)
      return 1;
   ll p = power(a, n / 2);
   p = p * p;
   if (n & 1)
      p = p * a;
   return p;
}
//recursive approach to count
//discarded sub sequences
void solve(int i, int n, float sum, float k,
float* a, float* prefix){
   if (sum > k) {
      discard_count += power(2, n - i);
      return;
   }
   if (i == n)
      return;
      float rem = prefix[n - 1] - prefix[i];
   if (sum + a[i] + rem > k)
      solve(i + 1, n, sum + a[i], k, a, prefix);
   if (sum + rem > k)
      solve(i + 1, n, sum, k, a, prefix);
}
int countSubsequences(const int* arr,
int n, ll K){
   float sum = 0.0;
   float k = log2(K);
   float prefix[n], a[n];
   for (int i = 0; i < n; i++) {
      a[i] = log2(arr[i]);
      sum += a[i];
   }
   prefix[0] = a[0];
   for (int i = 1; i < n; i++) {
      prefix[i] = prefix[i - 1] + a[i];
   }
   ll total = power(2, n) - 1;
   if (sum <= k) {
      return total;
   }
   solve(0, n, 0.0, k, a, prefix);
   return total - discard_count;
}
int main() {
   int arr[] = { 4, 8, 7, 2 };
   int n = sizeof(arr) / sizeof(arr[0]);
   ll k = 50;
   cout << countSubsequences(arr, n, k);
   return 0;
}

출력

9