FFT tricks in Competitive Programming.

  The FFT in Competitive Programming So I was grinding some problems on Codeforces last weekend when I came across yet another polynomial multiplication task. I coded a simple O(n²) approach, then Time limit exceeded.  That's when I realized I needed the Fast Fourier Transform (FFT) algorithm. If you're serious about competitive programming, FFT is one of those tools that you absolutely need in your arsenal. It transforms polynomial multiplication from an O(n²) pain into a O(n log n). Why FFT? Let's be real - FFT problems don't show up every day. But when they do, they're usually worth a lot of points. More importantly, understanding FFT gives you a powerful technique for dealing with convolutions and certain types of optimization problems. Some classic problem types where FFT shines: Polynomial multiplication String matching with wildcards Counting the number of ways to make a sum with given elements Substring problems that involve counting occurrences The C...