[ES] Sobre "Fast-Fourier Transform" y "Hadamard Transform" en programación competitiva

Estaba hablando con un amigo y me preguntó sobre el uso de FFT en programación competitiva. El texto de abajo surgió en esa conversación.

Fourier

La clave es que hay muchos problemas que se pueden resolver usando esta función:

// tenemos dos bolsas A y B con bolitas con números naturales
// queremos saber qué numeros se pueden formar tomando una bolita de A y una de B y sumando sus numeros
//
// a[i] es la cantidad de bolitas con el numero i en A
// b[j] es la cantidad de bolitas con el numero j en B
vector combinaciones(vector a, vector b) {
  int n = a.size(), m = b.size();
  vector c(n+m-1);
  forn(i,n) forn(j,m)
    c[i+j] += a[i] * b[j];
  return c;
}

Por otro lado, consideramos el producto de polinomios

// producto de polinomios A y B
// a[i] es el coeficiente de grado i de A
// b[j] es el coeficiente de grado j de B
vector producto_polinomio(vector a, vector b) {
  int n = a.size(), m = b.size();
  vector c(n+m-1);
  forn(i,n) forn(j,m)
    c[i+j] += a[i] * b[j];
  return c;
}

Por un tercer lado, pensamos la convolución de dos señales discretas y finitas

// convolucion de las señales A y B
// a[i] es A(i)
// b[j] es B(j)
vector convolucion(vector a, vector b) {
  int n = a.size(), m = b.size();
  vector c(n+m-1);
  forn(i,n) forn(j,m)
    c[i+j] += a[i] * b[j];
  return c;
}

Y *wow* las tres tienen el mismo código (capaz uno codearía distinto la convolucion pq la intuición es bastante distinta, pero sería equivalente)

Todo el chiste es que podes calcular eso en nlogn usando fft

vector convolucion(vector a, vector b) {
  int n = a.size(), m = b.size();
  vector fa = fft(a);      // nlogn
  vector fb = fft(b);      // nlogn
  vector fc(2*n);
  forn(i, n) fc[i] = fa[i] * fb[i]; // n
  return fft_inv(fc);               // nlogn
}

Hadamard

Esto no es tan común pero hay algunos problemas que se pueden resolver con esta función

// tenemos dos bolsas A y B con bolitas con números naturales
// queremos saber qué numeros se pueden formar tomando una bolita de A y una de B y haciendo OR binario de sus numeros
//
// a[i] es la cantidad de bolitas con el numero i en A
// b[j] es la cantidad de bolitas con el numero j en B
vector combinaciones(vector a, vector b) {
  int n = a.size(), m = b.size();
  vector c(max(n, m));
  forn(i,n) forn(j,m)
    c[i|j] += a[i] * b[j];
  return c;
}

Y bueno esto sale rápido con el mismo truco, pero usando hadamard en vez de fourier

vector convolucion_OR(vector a, vector b) {
  int n = a.size(), m = b.size();
  vector ha = ht(a);      // nlogn
  vector hb = ht(b);      // nlogn
  vector hc(max(n,m));
  forn(i, n) hc[i] = ha[i] * hb[i]; // n
  return ht_inv(hc);               // nlogn
}