c++ - 集合论的取组合问题

Question

给定一个大小为 N 的数组 A。数组 A 的子集的值定义为该子集中所有数字的乘积。我们必须返回数组 A %(10^9+7) 的所有可能非空子集的值的乘积。

例如数组 A {3,5}

` 值{3} = 3, 值{5} = 5， 值{3,5} = 5*3 = 15

答案 = 3*5*15 %(10^9+7)。

谁能解释一下问题背后的数学原理。我正在考虑通过组合来解决它以高效地解决它。

我试过使用蛮力，它给出了正确的答案，但速度太慢了。 下一个方法是使用组合。现在我认为如果我们把所有的集合都乘以这些集合中的所有数字，那么我们将得到正确的答案。因此，我必须找出一个数字在计算答案时出现了多少次。在示例中，5 和 3 都出现了 2 次。如果我们仔细观察，a 中的每个数字都会出现相同的次数。

Answer 1

您正朝着正确的方向前进。

设x 为给定数组A 的一个元素。在我们的最终答案中，x 出现了 p 次，其中 p 等于 A 的子集数> 可能包含 x。

如何计算p？一旦我们决定我们肯定会在我们的子集中包含 x ，我们对其余的 N-1 元素有两个选择:将它们包含在集合中或不包含它们。因此，我们得出结论 p = 2^(N-1)。

因此，A 的每个元素在最终产品中恰好出现 2^(N-1) 次。剩下的就是计算答案:(a1 * a2 * ... * an)^p。由于指数非常大，您可以使用 binary exponentiation用于快速计算。

正如 Matt Timmermans 在下面的评论中建议的那样，我们无需实际计算 p = 2^(N-1) 即可获得答案。我们首先计算乘积 a1 * a2 * ... * an。然后，我们简单地将此乘积平方 n-1 次。

对应的C++代码:

int func(vector<int> &a) {
    int n = a.size();
    int m = 1e9+7;
    if(n==0) return 0;
    if(n==1) return (m + a[0]%m)%m;

    long long ans = 1;

    //first calculate ans = (a1*a2*...*an)%m
    for(int x:a){
        //negative sign does not matter since we're squaring
        if(x<0) x *= -1;
        x %= m;
        ans *= x;
        ans %= m;
    }

    //now calculate ans = [ ans^(2^(n-1)) ]%m
    //we do this by squaring ans n-1 times
    for(int i=1; i<n; i++){
        ans = ans*ans;
        ans %= m;
    }

    return (int)ans;
}