Math -> FFT And NTT

Polynomial multiplication and convolution with roots of unity, integer-friendly NTTs, and transform implementation details.

• Topic slug: math/fft
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 2
• Repo companion pages: 0
• Curated external problems: 8

Microtopics

• convolution
• DFT
• roots-of-unity
• bit-reversal
• polynomial-multiplication
• NTT-prime
• primitive-root

Learning Sources

Source	Type
cp-algorithms FFT	Reference
OI Wiki FFT	Reference
AtCoder ACL Convolution	Primary

Practice Sources

Source	Type
AtCoder Practice2 F	Practice
CSES Signal Processing	Practice
CSES Apples and Bananas	Practice

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Convolution	AtCoder	Easy	Convolution, NTT, Polynomial Multiplication	Implementation; Math	Polynomial Convolution; Roots Of Unity	Number Theoretic Transform; Acl	The cleanest official practice problem for plain convolution under a prime modulus.
Convolution	Library Checker	Easy-Medium	Polynomial Multiplication, NTT	-	-	Convolution; 998244353	The standard NTT/convolution benchmark.
Convolution Mod	Library Checker	Medium	Polynomial Multiplication, NTT	-	-	Mod Convolution; NTT-Friendly; Formal Power Series	Same core idea but in the Library Checker format.
Fast Fourier Transform	AtCoder	Medium	Convolution	Math; Implementation	Complex Numbers; Polynomial Multiplication	Signal Processing	The canonical introductory FFT task and a very natural first heavy-convolution problem.

Stretch

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Divisor Set	Codeforces	Hard	Number Theory	Math; Divide-And-Conquer	Convolution; Divisor Structure	Divisors	A strong FFT-adjacent number theory problem where convolution appears inside a divisor lattice.
Function Sum	Codeforces	Hard	Combinatorics	Combinatorics; Math	FFT; Generating Functions	Generating Functions	A more advanced combinatorial setting where convolution is the right language.
Substring Search	Codeforces	Hard	Strings	Strings; Convolution	FFT Matching Ideas; String Hashing Basics	Substring Matching; Bitmasks	A challenging string task that benefits from efficient batch correlation.
Yet Another String Matching Problem	Codeforces	Hard	String-Matching	Strings; Convolution	FFT-Based Matching; Alphabet Encoding	Pattern Matching	A classic FFT-powered string matching problem with a memorable, reusable trick.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
CONVOLUTION	Convolution	primary	medium	-	Note	Code
POST2	A cộng B version 2	primary	medium	convolution; digit aggregation; big integer addition	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py