所有子集的乘积之和,

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

我上面给出的天真公式的优化是用每个新因子得到产品的模数,如果遇到零则使产品短路 - 如果主要因素(按照多重性计算)出现在该 (1 + a_i)

一个简单的测试:

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

这很容易用手验证.

压力测试:

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

nums 是一百万到一百万的随机数

当然,

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

由于存在在至少32个奇数nums(因此32号a_i为哪些1+a_i是偶数).

另一方面,1000003是一个大于1000000的素数,因此计算不会短路:

>>> sumProducts(nums,1000003)
719694

计算需要一秒钟.