Comments 7
спасибо, правда очень интересно, правда скорость придётся замерять самому, наверняка скорости разные, симд/несимд/сейф/ансейф/с/с++
просто сейчас всё обращено на некоторые аспекты, мы же не на спарке программируем
. 
Спасибо за интересную статью.
Не могли бы вы заодно расписать, как эта свертка применяется к оригинальной задаче.
Ведь N отсюда - это же 20 - количество друзей в задаче, верно? А 2^20 > M = 5*10^5 - количества кучек. Поэтому "наивное" решение за O(N^2 M), состоящее в переборе всех пар друзей и проходу по всем кучкам, будет даже быстрее этой свертки за O(N^2 2^N).
Или задача послужила только вдохновлением к этому методу?
Мы не можем перебрать все пары друзей, так как их 
. Поэтому нужно использовать приведённый алгоритм, но с некоторой вариацией.
Постараюсь кратко указать направление идеи.
В качестве 
и 
возьмем 
равное количеству друзей которые едят именно этот набор пицц.
Так же 
будет равен не размеру множества, а количеству пицц нечетного размера.
Делаем свертку 
, с самим собой перемножаем в 
и разворачиваем.
Тут нужно учесть, что ответ будет в 2 раза больше, и для 
, нужно удалить неподходящие случаи.
Так же у задачи есть разбор и пример кода.
Но эта задача сложная (*3000), и разбор будет большим, поэтому я постарался рассказать только направление идеи.
R - это поле, в данном случае число
Вы не про 
часом?
Быстрая свёртка множеств (алгоритм)