นับซับซีเควลที่ผลคูณ <= K แบบ Recursive ใน 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