#Fft

4 posts

Combinatorics #2-ex1 April 25, 2026 2 min read

Difference (Correlation) Convolution

Cross-correlation via ordinary convolution: reverse-A and reverse-B extraction methods, derivation, and Ring Trick II (cyclic shift score maximisation via difference convolution).

#math #combinatorics #fft #ntt #convolution

Combinatorics #2-ex2 April 25, 2026 5 min read

Cyclic Convolution

Cyclic convolution definition, FFT/NTT implementation for n=2^k, zero-padding, why n must be a power of two, and the fold-back technique for arbitrary n.

#math #combinatorics #fft #ntt #convolution

Combinatorics #2.1 April 25, 2026 10 min read

FFT and Lagrange Interpolation

Polynomial representations, FFT/DFT over complex numbers, Triple Sums, Fuzzy Search (difference convolution), FFT template, Lagrange interpolation (O(n²) and O(n) equidistant), sum of k-th powers, Assigning Prizes polynomial DP.

#math #combinatorics #fft #polynomial #lagrange

Combinatorics #2.2 April 25, 2026 12 min read

Primitive Roots, Discrete Logarithm, NTT, Divide-and-Conquer NTT

Order and primitive roots (Euler’s theorem, BSGS, exBSGS), discrete index as logarithm analogue, SGU 261 Discrete Roots, NTT theory and templates, divide-and-conquer NTT (product tree), Wannafly D team selection, Nowcoder 50F …

#math #combinatorics #ntt #primitive-root #bsgs