Sebastian Mestre's Algorithmic Adventures

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[