c++ - (可能是 NP-Hard)找到一个集合的子集总数，使得每个子集与其所有元素相乘时的值大于 X

Question

有一个大小为 n 的数组 arr。那么它的 2^n 子集中有多少个的总乘积大于某个数字(比如 X)？

n 约为 2^5，X 可以更大，约为 2^60(无论 C++ long 变量适合什么)

我认为类似于子集总和的东西会起作用，但我现在并不这么认为。

---

我从this question from a past contest想到了这一点来自 Codeforces。虽然这个问题不需要我问什么，但我很好奇。

Answer 1

您的问题可以通过动态编程按原样解决，即不使用日志。

当输入整数以二进制给出时(而不是 unary )， 你的问题是NP-hard在非自适应2查询减少下，因为:

number of subsets whose product equals X
=
number of subsets whose product is greater than X-1
−
number of subsets whose product is greater than X.

我没有立即看到任何显示实际 NP 硬度的方法(即，在 1 个查询减少下)。