как рассчитать свертку XOR (двоичную) с временной сложностью O (n log n)

введите здесь описание изображения

«⊕» — это побитовая операция XOR.

Я думаю, что алгоритм Карацубы можно использовать для решения проблемы, но когда я пытаюсь использовать XOR вместо + в алгоритме Карацубы, трудно получить подзадачу.


algorithm divide-and-conquer
person Ganlin Zh    schedule 03.12.2018    source источник
comment
Алгоритм Карацубы не O(n log n).   -  person Nelfeal    schedule 03.12.2018

Ответы (1)


arrow_upward
3
arrow_downward

теорема свертки дает вам

F(C) = F(A) . F(B)

где F — преобразование Фурье, в данном случае преобразование Адамара, а . — точечное умножение. Используя быстрое преобразование Уолша-Адамара, вы можете вычислить F(A), F(B) и, наконец, C (используя инверсию) в O(n log n) операциях. Точечное умножение просто O(n).

person Nelfeal    schedule 03.12.2018