Introduction to Fast Fourier Transform

Author: Benjamin Qi

Quickly multiplying polynomials

Status	Source	Problem Name	Difficulty	Tags	Solution	URL
	YS	Convolution Mod	Easy		View Solution
	YS	Convolution Mod 10^9+7	Normal		View Solution

Tutorial

Resources
cp-algo	FFT
CSA	FFT and Variations
CF	adamant - Lecture Notes
CF	FFT / NTT: The tough made simple Pt 1	also see Pt 2

Resources
Benq	FFT

Resources
Benq	FFTmod	NTT with three different moduli

The "multiplication with arbitrary modulus" described in cp-algo requires long double to pass.

Source	Problem Name	Difficulty	Solution
POI	2018 - Polynomial	Easy	View Solution
Kattis	K-Inversions	Easy	View Solution
Kattis	Matchings	Normal	View Solution
Kattis	Alien Codebreaking	Very Hard	Show Sketch

Status	Source	Problem Name	Difficulty	Tags	Solution	URL
	YS	Frequency Table of Tree Distance	Hard	Show Tags Centroid, FFT	View Solution
	DMOJ	Big Integer	Very Hard	Show Tags Centroid, FFT	Check DMOJ

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!