(可能是NP-Hard)找出集合的子集总数，这样当每一个子集与其所有元素相乘时，其值都大于X。

Question

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

n在2^5左右，X可以在2^60左右更大(只要适合于C++ long变量)

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

我从Codeforce的这个问题来自过去的一场比赛那里想过这个问题。虽然这个问题不需要我所要求的，但我很好奇。

Answer 1

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

当输入整数以二进制(而不是一元)的形式给出时，在非自适应的2-查询缩减下，您的问题是NP-硬的，因为：

乘积等于X的子集数 = 乘积大于X-1的子集数 − 乘积大于X的子集数。

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