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

Question

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

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

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

Answer 1

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

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

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