Преобразование Адамара
$xor$-свёртка
Если есть $n = 2^k$ и два массива $a$ и $b$ длиной $n$, то массив $c$ называется $xor$-свёрткой $a$ и $b$, если $$c[i] = \sum_{j\,xor\,k=i}^{n - 1} a[j] \cdot b[k]$$ То есть берутся все такие $j$ и $k$, что их побитовый $xor$ равен $i$, и к $c[i]$ прибавляются все такие $a[j] \cdot b[k]$.
Преобразование Адамара
Если есть $n = 2^k$ и массив $a$ длиной $n$. Тогда массив $b$ называется преобразованием Aдамара над массивом $a$, если $$b[i] = \sum_{j=0}^{n - 1} a[j] \cdot -1^{popcnt(i\&j)}$$ $popcnt(a)$ это количество 1 в двоичной записи числа $a$.
То есть берутся все $j$ и у всех берётся побитовое И с $j$, у результата $i\&j$ считается количество 1 в двоичной записи, и если это число чётно, то $a[j]$ прибавляется к $b[i]$, а иначе вычитается из $b[i]$.
Будем обозначать преобразование Адамара над массивом $a$ как $Adamar(a)$.
Преобразование Адамара можно рассмотреть в матричном виде. Можно сказать, что у нас есть массив $a$ как горизонтальный вектор: $$\begin{bmatrix}a_0 & a_1 & \cdots & a_{n - 1}\end{bmatrix}$$ И мы его хотим домножить на матрицу, состоящую из $-1$ и $1$, чтобы получить $Adamar(a)$. Такая матрица называется матрицей Адамара и мы будем её обозначать как $M_{A(n)}$.
Попробуем её найти. Для начала возьмём матрицу $n \times n$, состоящую из 1.
$$\begin{bmatrix} 1 & 1 & \cdots & 1 \\ \vdots & \vdots &\ddots &\vdots \\ 1 & 1 &\cdots & 1 \end{bmatrix}$$
Теперь заметим, что если мы возьмём 1 в столбце $x$ в строке $y$, и заменим её на $-1^{popcnt(x\&y)}$, то мы получим то, что нам надо.
Теперь осталось описать понятным языком как выглядит матрица Адамара. Покажем это рекурсивно через меньшие матрицы.
Матрица Адамара для $n = 1$ это просто матрица из единственной 1.
Найдём теперь матрицу Адамара для $n = 2^k$. Заметим, что если $x < n / 2$ и $y < n / $, то $(x + n / 2)\&y = x\&y$ и $x\&(y + n / 2) = x\&y$, а $(x + n / 3)\&(y + n / 2) = x\&y + n / 2$. Тогда если матрицу Адамара для $n$ разделить на 4 части, то верхняя правая, верхняя левая, нижняя левая будут одинаковы, и только нижняя правая будет равна каждой из них, с заменёнными 1 на -1 и -1 на 1.
То есть примеры матриц Адамара это:
$$\begin{bmatrix} 1 & 1 \\ 1 & -1 \\ \end{bmatrix}$$ $$\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \\ \end{bmatrix}$$ И каждая следующая это предыдущая, повторённая 2 раза по горизонтали и 2 по вертикали (то есть всего 4 раза) и нижняя правая домноженна на $-1$. $$M_{A(n)} = \begin{bmatrix} M_{A(n / 2)} & M_{A(n / 2)} \\ M_{A(n / 2)} & -1 \cdot M_{A(n / 2)} \\ \end{bmatrix}$$
Тогда преобразование Адамара можно записать в таком виде:
$$Adamar(a) = \begin{bmatrix}a_0 & a_1 & \cdots & a_{n - 1}\end{bmatrix} \cdot M_{A(n)}$$
Утверждение:
$Adamar(Adamar(a)) = a \cdot n$.
Доказательство:
Рассмотрим преобразование Адамара в матричном виде. Нам надо показать, что $a \cdot M_{A(n)} \cdot M_{A(n)} = a \cdot n$. То есть надо показать, что $$M_{A(n)} \cdot M_{A(n)} = \begin{bmatrix}
n & 0 & \cdots & 0 \\
0 & n & \cdots & 0 \\
\vdots & \vdots &\ddots &\vdots \\
0 & 0 &\cdots & n
\end{bmatrix}$$
(То есть получится матрица, у которой на диагонали $n$, а на всех остальных местах $0$)
Докажем по индукции от $n$. Для $n = 1$ очевидно. Если верно для $n / 2$, то так как мы знаем, $$M_{A(n)} = \begin{bmatrix} M_{A(n / 2)} & M_{A(n / 2)} \\ M_{A(n / 2)} & -M_{A(n / 2)} \\ \end{bmatrix}$$ Далее для удобства обозначим $M_{A(n / 2)}$ как $A$ Тогда $$M_{A(n)} \cdot M_{A(n)} = \begin{bmatrix} A \cdot A + A \cdot A & A \cdot A + A \cdot -A \\ A \cdot A + -A \cdot A & A \cdot A + -A \cdot -A \\ \end{bmatrix} = \begin{bmatrix} A \cdot A + A \cdot A & A \cdot A - A \cdot A \\ A \cdot A - A \cdot A & A \cdot A + A \cdot A \\ \end{bmatrix} = \begin{bmatrix} 2 \cdot A \cdot A & 0 \\ 0 & 2 \cdot A \cdot A \\ \end{bmatrix}$$ Ну тут уже или вы понимаете, что мы получили что хотели, или вы окончательно умираете от линала.
$xor$-свёртка через преобразование Адамара
Пусть $c$ это $xor$-свёртка $a$ и $b$. То есть
$$c[i] = \sum_{j\,xor\,k=i}^{n - 1} a[j] \cdot b[k]$$
Теперь применим к $c$ преобразование Адамара. Получим
$$Amdamar(c)[i] = \sum_{x=0}^{n - 1} c[x] \cdot -1^{popcnt(i\&x)} = \sum_{x=0}^{n - 1} \left(\sum_{y\,xor\,z=x}^{n - 1} a[y] \cdot b[z]\right) \cdot -1^{popcnt(i\&x)}$$
Дальше для каждой пары $y$ и $z$ они использовались только в одном $x$, потому что есть ровно одно число, равное $y\,xor\,z$. Тогда предыдущая жесть равна:
$$\sum_{y=0}^{n - 1} \sum_{z=0}^{n - 1} a[y] \cdot b[z] \cdot -1^{popcnt(i\&(y\,xor\,z))}$$
Теперь заметим, что $i\&(y\,xor\,z) = (i\&y)xor(i\&z)$. Тогда $popcnt(i\&(y\,xor\,z)) = popcnt((i\&y)xor(i\&z))$. А $popcnt(a\,xor\,b)$ по модулю 2 равно $popcnt(a) = popcnt(b)$. Тогда $-1^{popcnt(i\&(y\,xor\,z))} = -1^{popcnt(i\&y)} \cdot -1^{popcnt(i\&z)}$. Тогда предыдущаю жесть равна
$$\sum_{y=0}^{n - 1} a[y] \cdot -1^{popcnt(i\&y)} \cdot \sum_{z=0}^{n - 1} b[y] \cdot -1^{popcnt(i\&z)} = Adamar(a)[i] \cdot Adamar(b)[i]$$.
Тогда $Adamar(c)[i] = Adamar(a)[i] \cdot Adamar(b)[i]$. Тогда из предыдущего утверждениия получаем, что $$Adamar(c) = \frac{Adamar(Adamar(a) \cdot Adamar(b))}{n}$$.
Тогда если мы быстро умеем делать преобразование Адамара, то мы быстро умеем считать $xor$-свёртку.
Автор конспекта: Филипп Грибов
По всем вопросам пишите в telegram @grphil