Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

The SIMPLEST FFT explanation EVER!

Revision en1, by GuillermoFrancella, 2018-10-19 18:16:56

You know FFT can be used to solve a lot of hard problems that require multiplying two polynomials, for example yesterday's hardest problem. Also many string matching problems can be transformed into an analogous polynomial problem and be solved using FFT.

Have you ever tried studying FFT but gave up because it was too mathy and difficult to understand?

Well, that won't happen anymore! Because a kind programmer who goes by the handle of RiAst decided to write a tutorial so that we, the ones who don't know much math, can finally understand and implement FFT. Here's the Ultimate Guide to understanding FFT once and for all!

Without furthed ado, here's the link to said glorious tutorial: Simple FFT Tutorial by RiAst

Tags fft, simple, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English GuillermoFrancella 2018-10-19 18:16:56 815 Initial revision (published)