Table of Contents

Tutorial Solution - Convolution Mod Solution - Convolution Mod 10^9+7 Note - FFT Killer Problems On a Tree Edit on Github

Has Not Appeared

0/8

Introduction to Fast Fourier Transform

Author: Benjamin Qi

Quickly multiplying polynomials

Table of Contents

Tutorial Solution - Convolution Mod Solution - Convolution Mod 10^9+7 Note - FFT Killer Problems On a Tree

Status	Source	Problem Name	Difficulty	Tags	Solution
	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

Solution - Convolution Mod

Resources
Benq	FFT

Solution - Convolution Mod $10^9+7$

Resources
Benq	FFTmod	NTT with three different moduli

Note - FFT Killer

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

Problems

Status	Source	Problem Name	Difficulty	Tags	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

On a Tree

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

Module Progress:

Give Us Feedback on Introduction to Fast Fourier Transform!

Join the Discussion!

Feel free to voice your thoughts in the comments section.

Need help? Join the USACO Forum!