Term

Convolution

Index

All notes

2026.04.28

Number Theory #0: Common Formulae — Legendre's Formula & Divisor Convolutions

Legendre’s formula, divisor and multiple convolutions in O(n log n), offline-difference batch processing for H(n)=Σf(d)g(⌊n/d⌋).

#math #number-theory #convolution #divisor #legendre

2026.04.25

Combinatorics 2 min read

Combinatorics #2-ex1: 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

2026.04.25

Combinatorics 5 min read

Combinatorics #2-ex2: 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

2026.04.25

Combinatorics 10 min read

Combinatorics #2.1: 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 …

#math #combinatorics #fft #polynomial #lagrange