[T3] Solucionar el problema usando polinomios

[raimundomartinez]

Hola! Que llevo como 2 días pensando mucho en el problema de la T3 y buscando ayuda en internet y estoy muy pegado. Mi problema es, que para lograr que sea O(nlogn) se debe solucionar el problema usando TAN SOLO UNA multiplicación de polinomios (porque si uno usa múltiples la solución que n^2 log n o algo así). No se si me podrían dar alguna pista o guiarme un poco más al respecto de como solucionar el problema usando polinomios. Se apreciaría mucho.

Saludos,

[N9199]

Hola Raimundo, te recomiendo que pienses en el hint y que busques usos clásicos de FFT con strings. Esas dos cosas deberían ayudar, en general esta clase de problema es pensar cómo usar información de índices con multiplicar polinomios (hacer una convolución) para generar información sobre el problema original y usar esa información para resolver el problema.