O(n * sqrt(k)) to count subsequences with product less than k

subsequences_product.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, k; cin >> n >> k; vector<int> a;
  for (int i = 0; i < n; ++i) {
    int cur; cin >> cur;
    a.push_back(cur);
  }

  --k; // to work with <= instead of <

  int z = 0;
  for (int i = 0; i < n; ++i) {
    z += a[i] == 0;
  }

  int rs = ((1 << z) - 1) * (1 << (n - z));

  vector<int> b;
  for (int i = 0; i < n; ++i) {
    if (a[i] != 0) {
      b.push_back(a[i]);
    }
  }

  a = b;
  n = a.size();

  if (n == 0) {
    cout << rs << endl;
    return 0;
  }

  int sqk = (int) ceil(sqrt(k));
  int small[n][sqk + 1];
  int large[n][sqk + 1];

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= sqk; ++j) {
      if (i == 0) {
        small[0][j] = (a[0] <= j) + (j >= 1);
      } else {
        small[i][j] = small[i - 1][j] + small[i - 1][j / a[i]];
      }
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= sqk; ++j) {
      if (i == 0) {
        if (j == 0) large[0][0] = 1;
        else large[0][j] = (a[i] <= (k / j)) + 1;
        continue;
      }

      large[i][j] = large[i - 1][j];
      if (j * a[i] <= sqk) {
        large[i][j] += large[i - 1][j * a[i]];
      } else {
        large[i][j] += small[i - 1][k / (j * a[i])];
      }
    }
  }

  rs += large[n - 1][1] - 1; // subtract empty subsequence
  cout << rs << endl;

  return 0;
}