所有子集的乘积之和，

Question

我想计算给定 $N$ 元素集的每个子集的乘积之和。例如，给定集合 {1, 2, 3}，答案是 1 + 2 + 3 + 1 * 2 + 1 * 3 + 2 * 3 + 1 * 2 * 3。我也想给出模 $ 的答案M$.

我所知道的是我可以计算 $(x - a_1)(x - a_2)...(x - a_n) - 1$，但是将涉及 FFT，因此可能存在一些舍入误差，但该想法的主要问题是它需要 $O(N \log^2 N)$ 时间并且做模 $M$ 是有问题的。有没有更快的方法来解决这个问题？这不是我的作业，我从老师那里得到了这个任务来练习编程比赛，但我真的卡在了这个问题上。

约束条件：

$a_i\le 10^9$

$N\le 10^6$

$M\le 10^9$

Answer 1

有问题的总和是

[(1+a_1)*(1+a_2)*(1+a_3)*...*(1+a_N) - 1] (mod M)

这是

[(1+a_1)%M * (1+a_2)%M * ... * (1+a_N)%M - 1] % M

如果你能做得更好，我会很惊讶。

这是一个 Python 实现：

def sumProducts(nums, M):
    p = 1
    for num in nums:
        p = p*((1+num)%M)%M
        if p == 0:
            return M-1
    return (p-1)%M

我上面给出的朴素公式的优化是对每个新因子取乘积的模数，如果遇到零则 short-circuit 乘积 - 如果素数因子 (根据多重性计数）出现在 (1 + a_i)

一个简单的测试：

>>> sumProducts([1,2,3],5)
3

这很容易用手验证。

一个stress-test:

>>> from random import randint
>>> nums = [randint(1,1000000) for i in range(100000)]

nums是1到100万范围内的一百万个随机数

当然，

>>> sumProducts(nums,2**32)
4294967295

因为 nums 中至少有 32 个奇数（因此 a_i 中有 32 个数 1+a_i 是偶数）。

另一方面，1000003是大于1000000的质数，所以计算不short-circuit:

>>> sumProducts(nums,1000003)
719694

计算时间不到一秒。

所有子集的乘积之和，

Sum of products of all subsets,

algorithm

combinatorics

number-theory

polynomials