Practice
Pick a Codeforces problem, write a solution in Python or C++, and grade it locally against the public sample tests.
Count length-n strings over an allowed digit set whose digit sum equals exactly half the maximum possible. Reduces to raising a digit-frequency polynomial to the n/2 power via FFT/NTT.
Determine all total values that can be reached by picking exactly k items (with repetition) from a list of n prices. Solved via polynomial exponentiation of the indicator polynomial.
For every k in [1..K], count the number of ways to partition n balls into k labelled groups of one or two adjacent balls. Solve with NTT-accelerated matrix exponentiation on generating-function polynomials.
Runs in your browser via Pyodide (WebAssembly).
Output of “Run custom input” will appear here.Sample 1
Input
4 2 1 8
Expected output
6
Sample 2
Input
20 1 6
Expected output
1
Sample 3
Input
10 5 6 1 4 0 3
Expected output
569725
Approximate arithmetic operations vs polynomial degree. Log scale on y-axis — notice how O(n²) diverges rapidly while both FFT variants stay near-flat.
Recursive FFT ≈ 4·n·log₂n ops (complex butterfly). Iterative FFT ≈ 3·n·log₂n (same passes, no recursion overhead). Naive = n² multiply-accumulates.
Naive O(n²) vs FFT O(n log n) polynomial multiplication, measured in your browser. Results may vary by device — larger degrees expose the gap most clearly.
Running benchmark… naive multiply may be slow for large n.
Polynomial Multiplication
Direct FFT application — given two polynomials, compute their product. The canonical entry-level FFT problem.
ATC001-C — Fast Fourier Transform
Classic AtCoder introduction: count the number of ways to pick one element each from two arrays such that their sum equals each target.
CF 1257G — Divisor Set
Divide-and-conquer FFT: multiply together the linear factors of a large polynomial without materialising the full product at each step.
CF 993E — Nikita and Order Statistics
Count pairs of subarrays with specific prefix-sum properties. Reduces to a circular convolution solvable with FFT over the prefix-sum array.
FFT tutorial & template
Comprehensive walkthrough of recursive FFT, iterative FFT, and NTT with ready-to-paste C++ code.
Introduction to FFT (jakobkogler)
Step-by-step derivation from polynomials to the butterfly operation, with intuition on why the algorithm works.