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

Я хочу вычислить сумму произведения каждого подмножества заданного набора элементов $N$. Например, для набора {1, 2, 3} ответ равен 1 + 2 + 3 + 1 * 2 + 1 * 3 + 2 * 3 + 1 * 2 * 3. Я также хотел бы дать ответ по модулю $ М$.

Что я знаю, так это то, что я мог бы вычислить $(x - a_1)(x - a_2)...(x - a_n) - 1$, но это потребовало бы быстрого преобразования Фурье, поэтому могут быть некоторые ошибки округления, но основная проблема с эта идея состоит в том, что это занимает $O(N \log^2 N)$ времени и выполнение по модулю $M$ проблематично. Есть ли более быстрый способ решить эту проблему? Это не моя домашняя работа, я получил это задание от своего учителя, чтобы потренироваться перед соревнованием по программированию, но я действительно застрял на этой задаче.

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

$a_i \le 10^9$

$N \le 10^6$

$M \le 10^9$


algorithm polynomials combinatorics number-theory
person user128409235    schedule 21.01.2016    source источник
comment
1. Пожалуйста, укажите ссылки на ваши источники. Можете ли вы отредактировать вопрос, чтобы указать конкретный источник, из которого возникла эта проблема? 2. Мы хотим помочь вам понять, а не просто решить за вас вашу практическую задачу. Решение вашей практической задачи за вас не поможет ни вам, ни кому-либо еще. В частности, единственный способ стать лучше в этом — проработать это самостоятельно.   -  person D.W.    schedule 11.10.2016

Ответы (1)


arrow_upward
5
arrow_downward

Сумма, о которой идет речь,

[(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

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

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

>>> sumProducts(nums,1000003)
719694

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

person John Coleman    schedule 21.01.2016
comment
Это линейно O(N), так что непобедимо. (Возьмите модуль после каждого умножения, чтобы избежать переполнения.) - person Yves Daoust; 21.01.2016
comment
Очень элегантный, короткий сладкий и простой - person novice; 21.01.2016
comment
@YvesDaoust Я считал, что часть о том, как использовать модуль на каждом шаге, ясна из контекста, хотя, безусловно, это хорошая идея, чтобы сделать это явным. Спасибо. - person John Coleman; 21.01.2016
comment
@JohnColeman: из-за использованного вами интервала можно подумать, что модуль просто применяется к непосредственному левому аргументу. Вы можете заключить в скобки (...((1+a_1)%M * (1+a_2))%M * ... * (1+a_N))%M. - person Yves Daoust; 21.01.2016
comment
@YvesDaoust Вы правы в том, что в написанной формуле нет ничего о том, чтобы брать модуль на каждом шаге (поскольку для этого потребуются глубокие скобки), но %M в конце ясно дает понять, что весь продукт вычисляется по модулю M, при этом он является деталь реализации, что для эффективного вычисления этого вы берете модуль на каждом шаге. С другой стороны, то, что кажется очевидным тому, кто знаком с модулярной арифметикой, может быть не очевидным для всех, поэтому хорошо было бы уточнить эту деталь. - person John Coleman; 21.01.2016