# Convolución XOR
Dados dos arreglos $A=[a_0, a_1, a_2, \dots, a_{2^k-1}]$ y $B=[b_0, b_1, b_2, \dots, b_{2^k-1}]$ de tamaño $2^k$, decimos que su **convolución XOR** es el arreglo arreglo $C=[c_0, c_1, c_2, \dots, c_{2^k-1}]$ de tamaño $2^k$, tal que su $i$-ésimo elemento es:

$$
\begin{align}
c_i &= \sum_{\substack{0 \leq j, k < 2^k \\ j \oplus k = i}} a_j \cdot b_k \\
&= \sum_{0 \leq j < 2^k} a_j \cdot b_{i \oplus j}
\end{align}
$$

donde $\oplus$ es el operador XOR a nivel de bits. Dicho de otra forma, $c_i$ es la suma del producto de un elementon de $A$ por un elemento de $B$, tal que el XOR de sus índices es $i$. Notemos que el tamaño de $C$ también será $2^k$, a diferencia de la convolución convencional. Por la naturaleza del XOR, estaremos trabajando sólo con arreglos de tamaño potencia de $2$.

:::info
:information_source: **Ejemplo 1**
Si tenemos los arreglos $A=[5,3,1,0]$ y $B=[2,0,1,3]$, tenemos que los elementos de $C$ serán:

\begin{align}
C_0 &= a_0b_0+a_1b_1+a_2b_2+a_3b_3 \\
&= 5 \cdot 2 + 3 \cdot 0 + 1 \cdot 1 + 0 \cdot 3 \\
&= 11
\end{align}

\begin{align}
C_1 &= a_0b_1+a_1b_0+a_2b_3+a_3b_2 \\
&= 5 \cdot 0 + 3 \cdot 2 + 1 \cdot 3 + 0 \cdot 1 \\
&= 9
\end{align}

\begin{align}
C_2 &= a_0b_2+a_1b_3+a_2b_0+a_3b_1 \\
&= 5 \cdot 1 + 3 \cdot 3 + 1 \cdot 2 + 0 \cdot 0 \\
&= 16
\end{align}

\begin{align}
C_3 &= a_0b_3+a_1b_2+a_2b_1+a_3b_0 \\
&= 5 \cdot 3 + 3 \cdot 1 + 1 \cdot 0 + 0 \cdot 2 \\
&= 18
\end{align}

Por lo tanto, $C=[11,9,16,18]$.
:::

### Convolución XOR como multiplicación de polinomios
En algunas ocasiones, nos conviene interpretar una convolución en términos algebraicos como una multiplicación de polinomios, en donde los elementos de $A$ y $B$ son los coeficientes de los operandos y los elementos de $C$ son los coeficientes del producto de $A$ por $B$. Esto puede facilitar modelar un problema, o facilitar la explicación de un algoritmo, que es el caso de estas notas.

Definamos un anillo donde $x^a \cdot x^b = x^{a \oplus b}$, es decir, cuando se multipliquen términos con bases iguales, en vez de sumar los exponentes, se sacará su XOR. De esta forma, si tenemos dos polinomios $A(x)=a_0+a_1x^1+a_2x^2+\dots a_{2^k-1}x^{2^k-1}$ y $B(x)=b_0+b_1x^1+b_2x^2+\dots b_{2^k-1}x^{2^k-1}$, su producto será:

$$
\begin{align}
A(x) \cdot B(x) &= \sum_{i=0}^{2^k-1} \sum_{j=0}^{2^k-1} a_i x^i \cdot b_j x^j \\
&= \sum_{i=0}^{2^k-1} \sum_{j=0}^{2^k-1} a_i b_j \cdot x^{i \oplus j} \\
&= \sum_{i=0}^{2^k-1} c_ix^i \\
&= C(x)
\end{align}
$$

Notemos que los coeficientes del producto coinciden con los elementos de $C$, ya que los términos del producto cuyos exponentes den el mismo XOR se van a sumar.

:::info
:information_source: **Ejemplo 2**
Tomemos los mismos arreglos del ejemplo $1$ y transformemoslos en polinomios: $A(x)=5+3x_1+1x_2$ y $B(x)=2+x^2+3x^3$.

Se puede comprobar que su producto $(5+3x_1+1x_2) \cdot (2+x^2+3x^3)$ será igual a $11+9x+16x^2+18x^3$ en el anillo que definimos. Los coeficientes del producto coinciden con $C$ del ejemplo $1$.
:::

## Transformada Rápida de Walsh-Hadamard (FWHT)
### Prerrequisitos
Me voy a basar en la multiplicación de polinomios de varias variables con FFT para explicar la FWHT (Fast Walsh-Hadamard Transform). Se pueden checar las siguientes notas para entender la idea de cómo usar la FFT para dicha multiplicación: https://hackmd.io/@8iUL97mRS2mgfTEJDy5xmA/SynR0fqwA

Hay explicaciones alternativas que no necesitan FFT en múltiples variables, como por ejemplo:
- https://www.serbanology.com/vault/A%20Bitwise%20Convolution%20Tutorial
- https://github.com/IvanAli/logical-convolutions/blob/main/logical_convolutions.pdf (capítulos 3 y 4)

Sin embargo, sabiendo mutiplicar polinomios en varias variables con FFT, es fácil usarlo para obtener la FWHT.

### Usando variables para cada bit
El XOR es una operación que se hace bit por bit, donde cada bit es independiente de los demás. El bit del resultado será $0$ si la suma de los bits en esa posición es par, y $1$ si la suma de los bits en esa posición es impar, como se puede ver en la siguiente tabla.

| a | b | Suma | XOR |
| - | - | - | - |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 2 | 0 |

Podemos explotar esta propiedad. Primero partiremos a la $x$ de cada término $a_ix^i$ en $k$ variables diferentes $x_0,x_1, \dots, x_{k-1}$, donde tendremos una variable para cada bit y su exponente será $1$ si ese bit está prendido en la representación binaria de $i$, o $0$ en caso contrario.

:::info
:information_source: **Ejemplo 3**
Si tenemos el polinomio $A(x)=5x^0+3x^3+4x^6+x^7$, entonces así quedaría la representación de cada término:

- $5x^0$ quedaría como $5x_0^0x_1^0x_2^0$, ya que el $0$ es $000$ en binario.
- $3x^3$ quedaría como $3x_0^1x_1^1x_2^0$, ya que el $2$ es $011$ en binario.
- $4x^6$ quedaría como $4x_0^0x_1^1x_2^1$, ya que el $6$ es $110$ en binario.
- $x^7$ quedaría como $x_0^1x_1^1x_2^1$, ya que el $7$ es $111$ en binario.

Finalmente, $A(x_0,x_1,x_2)$ sería igual a $5x_0^0x_1^0x_2^0 + 3x_0^1x_1^1x_2^0 + 4x_0^0x_1^1x_2^1 + x_0^1x_1^1x_2^1$.
:::

Esta representación es conveniente, ya que si hacemos la multiplicación convencional (en la que se suman los exponentes de bases iguales) de dos terminos en esta representación, el exponente de cada variable nos dira la suma de los bits en cada posición, y si tomamos esa suma módulo $2$, entonces nos dará el valor de cada bit en el XOR.

:::info
:information_source: **Ejemplo 4**
Consideremos los términos $3x^{12}$ y $4x^5$. Su producto es $12x^{12 \oplus 5}=12x^9$.

Ahora usemos la representación descrita. $3x^{12}$ es $3x_0^0x_1^0x_2^1x_3^1$, y $4x^5$ es $3x_0^1x_1^0x_2^1x_3^0$. Al hacer la multiplicación convencional (en la que se suman los exponentes), tenemos:

$$
(3x_0^0x_1^0x_2^1x_3^1) \cdot (4x_0^1x_1^0x_2^1x_3^0) = 12x_0^1x_1^0x_2^2x_3^1
$$

Lo que nos da la suma de cada bit en los exponentes, y al tomar los exponentes módulo $2$, obtenemos el valor de cada bit en el XOR:

$$
12x_0^{1 \% 2}x_1^{0 \% 2}x_2^{2 \% 2}x_3^{1 \% 2} = 12x_0^1x_1^0x_2^0x_3^1
$$

Lo que nos dice que la representación binaria del exponente es $1001$, es decir el exponente es $9$.
:::

Ahora podemos decribir un algoritmo para obtener la convolución XOR:

1. Transformar los polinomios $A$ y $B$ de grado $2^k-1$ a polinomos con $k$ variables, una variable para cada bit.
2. Multiplicar los polinomios con el [método de la FFT en multiples variables](https://hackmd.io/@8iUL97mRS2mgfTEJDy5xmA/SynR0fqwA#Multiplicaci%C3%B3n-de-polinomios-de-m%C3%A1s-de-dos-variables).
3. Aplicar módulo $2$ a los exponentes de cada término del producto.
4. Usar la representación binaria de los exponentes para obtener el exponente en representación decimal.

Recordemos que para multiplicar polinomios donde el resultado tiene grado $n$, requerimos que la FFT los evalúe en $2^l$ valores distinos, tal que $2^l>n$. Por lo tanto, en este caso necesitamos que cada variable sea evaluada en $4$ valores distintos, por lo que requerimos ajustar el polinomio para que tenga tamaño $4\cdot4\cdot4\cdot\ldots\cdot4=4^k$, y hacer un recorrido por cada variable sobre todos los términos. La complejidad sería $O(k4^k\log(4))=O(k4^k)$.

### Utilizando convolución circular
El tercer paso del algoritmo es aplicar módulo $2$ a los exponentes del producto. Sin embargo, podemos usar [convolución circular](https://hackmd.io/@alaneos777/H1KuU5ftw#Convoluci%C3%B3n-circular) para aplicar módulos en los exponentes: si evaluamos en sólo $2$ valores distintos a cada variable, entonces al hacer la multiplicación se estaría aplicando módulo $2$ de forma implícita (y esto es cierto para cualquier módulo, no sólo $2$).

Si no ajustamos el tamaño del polinomio y sólo lo evaluamos en dos valores distintos para cada variable con la FFT, ya se estaría aplicando módulo $2$ y la complejidad quedaría igual a $O(k2^k)$, la cual es la mejor complejidad que podemos obtener.

### Implementación
Así como está descrito el algoritmo con convolución circular, podríamos implementar la convolución creando un arreglo de $k$ dimensiones, donde cada dimensión tiene tamaño $2$ y [aplicar el método descrito en las notas de FFT 2D](https://hackmd.io/@8iUL97mRS2mgfTEJDy5xmA/SynR0fqwA#Multiplicaci%C3%B3n-de-polinomios-de-m%C3%A1s-de-dos-variables). Sin embargo, podemos simplificar mucho la implementación haciendo unas cuantas observaciones.

Primero, si vamos a evaluar cada variable en dos valores distintos con la FFT, entonces las evaluaremos en $\omega^0$ y $\omega^1$, donde $\omega$ es la segunda raíz de la unidad, la cual es $-1$. La primera consecuencia es que ya no necesitamos trabajar con números complejos. Otra consecuencia de esto, es que sólo necesitamos evaluar cada variable en $1$ y $-1$, por lo que si tenemos un polinomio $P(x)=p_0+p_1x$, entonces obtendríamos los siguientes valores:

$$
\begin{align}
P(1)=p_0+p_1 \\
P(-1)=p_0-p_1
\end{align}
$$

Otra observación es que cuando estemos aplicando FFT sobre la $i$-ésima variable, entonces vamos a aplicar FFT sobre polinomios formados por parejas de elementos cuyo exponente son diferentes sólo en el $i$-ésimo bit (y son iguales en los demás bits).

:::info
:information_source: **Ejemplo 5**
Queremos aplicar FFT al polinomio $A(x_0,x_1)=a_{0}x_0^0x_1^0+a_{1}x_0^1x_1^0+a_{2}x_0^0x_1^1+a_{3}x_0^1x_1^1$. Su representación en matriz es:

$$
\begin{bmatrix}
a_0&a_2\\
a_1&a_3\\
\end{bmatrix}
$$

Al aplicar FFT sobre las filas, la FFT se hace sobre índices que sólo son diferentes en el bit $1$.

$$
\begin{bmatrix}
a_0&a_2\\
a_1&a_3\\
\end{bmatrix}
\xrightarrow{\text{FFT por filas}}
\begin{bmatrix}
a_0+a_2&a_0-a_2\\
a_1+a_3&a_1-a_3\\
\end{bmatrix}
$$

Después, al aplicar FFT en las columnas, la FFT se hace sobre índices que sólo son diferentes en el bit $0$:

$$
\begin{bmatrix}
a_0+a_2&a_0-a_2\\
a_1+a_3&a_1-a_3\\
\end{bmatrix}
\xrightarrow{\text{FFT por columnas}}
\begin{bmatrix}
a_0+a_1+a_2+a_3&a_0+a_1-a_2-a_3\\
a_0-a_1+a_2-a_3&a_0-a_1-a_2+a_3\\
\end{bmatrix}=
\begin{bmatrix}
A(1,1)&A(1,-1)\\
A(-1,1)&A(-1,-1)\\
\end{bmatrix}
$$
:::

La idea presentada en el ejemplo $5$ se puede extender a $3$ o más bits.

Tomando en cuentas esas observaciones, podemos hacer la FWHT en un sólo arreglo, iterando sobre cada bit y haciendo la FFT sobre elementos cuyo índice sólo sea diferente el bit sobre el que estamos iterando. Podemos hacer la transformada con el siguiente código sencillo:

void FWHT (int A[], int k) {
    for (int j = 0; j < k; j++)
        for (int i = 0; i < (1 << k); i++)
            if (~i & (1 << j)) {
                // Sólo aplicamos FFT cuando se cumpla esta condición para evitar 
                // aplicar FFT dos veces sobre el mismo par de elementos.
                int p0 = A[i];
                int p1 = A[i | (1 << j)];
                
                A[i] = p0 + p1;
                A[i | (1 << j)] = p0 - p1;
            }
}

:::warning
**Nota**
Recordar que no importa en qué orden procesemos los bits, podríamos hacerlo desde el bit $k-1$ hasta el $0$ también.
:::

Para la FFT inversa, tenemos que:

$$
\begin{align}
p_0=\frac{P(1)+P(-1)}{2} \\
p_1=\frac{P(1)-P(-1)}{2}
\end{align}
$$

Esto se puede comprobar con la definición de FFT inversa o resolviendo un sistema de ecuaciones.

En el método de FFT en multiples variables vimos que para sacar la inversa, se tenía que hacer FFT inversa sobre cada viarable. Podemos usar el mismo argumento que antes para decir que al hacer inversa sobre la $i$-ésima variable, se hace inversa sobre todos los pares de valores cuyo índice sólo es diferente en el $i$-ésimo bit, por lo que el código de la FWHT inversa queda igual sólo que ahora dividimos entre $2$.

void FWHT (int A[], int k, int inv) {
    for (int j = 0; j < k; j++)
        for (int i = 0; i < (1 << k); i++)
            if (~i & (1 << j)) {
                int p0 = A[i];
                int p1 = A[i | (1 << j)];
                
                A[i] = p0 + p1;
                A[i | (1 << j)] = p0 - p1;
                
                if (inv) {
                    A[i] /= 2;
                    A[i | (1 << j)] /= 2;
                }
            }
}

Ya tenemos el código de la FWHT y su inversa, ahora el código de la convolución XOR quedaría así:

void XOR_conv (int A[], int B[], int C[], int k) {
    FWHT(A, k, false);
    FWHT(B, k, false);
    
    for (int i = 0; i < (1 << k); i++)
        C[i] = A[i] * B[i];
    
    FWHT(A, k, true);
    FWHT(B, k, true);
    FWHT(C, k, true);
}

:::warning
**Nota**
Al igual la FFT, la FWHT sólo funciona en arreglos de tamaño potencia de 2.
:::

### Convolución XOR módulo $p$
La convolución XOR también funciona cuando a los coeficientes se les aplica módulo un primo $p$, sólo habría que modular entre $p$ después de cada operación.

## Extras
### Convoluciones AND y OR
La FWHT se puede modificar para hacer convoluciones AND y OR. La explicación que más me gusta de esas modificaciones son a partir de la SOS DP, como se explica en el siguiente blog:

https://codeforces.com/blog/entry/115438

### Convoluciones GCD y LCM
La idea de aplicar SOS DP para obtener las convoluciones AND y OR se puede extender para obtener las convoluciones GCD y LCM. En el mismo [blog](https://codeforces.com/blog/entry/115438) se da una idea de cómo hacerlo.

## Problemas

### Medio
- [Buying Piles of Stones](https://codeforces.com/gym/102218/problem/B)

### Muy díficil
- [Games](https://codeforces.com/gym/102978/problem/G)
- [Triple](https://codeforces.com/problemset/problem/1119/H)