FFT Ladder

Who This Is For

Use this ladder when you already know arrays and counting, and you want to learn when a scary pair-counting problem is secretly just convolution.

Warm-Up

• understand convolution as pair counting
• frequency arrays with coordinate shifting

Core

• implement iterative FFT
• convert pair-sum or pair-difference counting into convolution
• exact modular convolution under 998244353

Stretch

• precision pitfalls
• POST2

Build Path

• floating FFT starter -> fft.cpp
• exact modular convolution -> ntt.cpp

Reopen Theory Pages

• quick theory refresher -> FFT / NTT
• counting precheck -> Counting Basics

Repo Anchors And Compare Points

• direct repo note -> POST2
• direct exact-mod note -> Convolution
• compare floating vs exact viewpoints -> FFT / NTT
• if one convolution is already trusted and the statement now wants inverse/log/exp under x^n -> Polynomial / Formal Power Series
• reopen the counting lens before the transform lens -> Counting Basics
• if coefficient shifts or mod arithmetic are the real bottleneck -> Modular Arithmetic ladder

The intended loop is:

1. first reduce the statement to a clean convolution story
2. compare against POST2 for the floating-counting branch or Convolution for the exact modular branch
3. only then decide whether fft.cpp or ntt.cpp is the better build path

Exit Criteria

You are ready to move on when you can:

• rewrite a pair problem as coefficient multiplication
• choose sensible array bounds and shifts
• explain why FFT changes O(n^2) pair work into O(n log n)
• tell when FFT is unnecessary because the direct solution is already small enough

External Practice

• CP-Algorithms - FFT
• KACTL

Tutorial Link

• FFT And NTT