Concepts6
Generating Functions - OGF
An ordinary generating function (OGF) encodes a sequence (a_n) as a formal power series A(x) = \sum_{n \ge 0} a_n x^n.
Primitive Roots
A primitive root modulo n is a number g that cycles through all units modulo n when you repeatedly multiply by g, so its multiplicative order equals \(\varphi(n)\).
Polynomial Operations
Fast polynomial operations treat coefficients like numbers but use FFT/NTT to multiply in O(n \log n) time instead of O(n^2).
Convolution Applications
Convolution turns local pairwise combinations (like matching characters or adding two dice) into a single fast transform–multiply–inverse pipeline.
NTT (Number Theoretic Transform)
The Number Theoretic Transform (NTT) is an FFT-like algorithm that performs discrete convolutions exactly using modular arithmetic instead of floating-point numbers.
FFT (Fast Fourier Transform)
FFT converts a polynomial from coefficients to values at the n-th roots of unity in O(n log n) time, enabling fast multiplication via pointwise products.