Сумма продуктов всех подмножеств,

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 $, но это связано с БПФ, поэтому могут быть некоторые ошибки округления, но основная проблема с этой идеей заключается в том, что она берет $ O (N \ log^2 N) $ time и делает modulo $ M $ проблематичной. Есть ли более быстрый способ решить эту проблему? Это не моя домашняя работа, я получил эту задачу от своего учителя, чтобы практиковать на конкурсе программирования, но я действительно застрял в этой проблеме.

Ограничение:

$ a_i \ ль 10^9 $

$ N \ ль 10^6 $

$ M \ ль 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 в миллион случайных чисел в диапазоне от 1 до миллиона

конечно,

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

, так как есть, по крайней мере, 32 нечетные числа в nums (отсюда 32 номера a_i, для которых 1+a_i равно).

с другой стороны, 1000003 простое число, которое больше, чем 1000000, так что вычисление не короткого замыкания:

>>> sumProducts(nums,1000003) 
719694 

Вычисление занимает менее одной секунды.