Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
O(n * sqrt(k)) to count subsequences with product less than k
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.