Convolution

$c_k={\sum }_{i+j=k}{a}_i{b}_j.$

The single most important operation in this branch. Recognising a convolution turns an $O(n^2)$ double loop into $O(n\log n)$.

Recognising one

You have a convolution whenever the answer at index $k$ sums over all pairs of indices combining to $k$:

Problem	Combination
Polynomial multiplication	$i+j=k$
”Number of ways to get sum $k$ from two sets”	$i+j=k$
Count pairs at distance $k$	$i-j=k$ (reverse one array)
String matching with wildcards	correlation
Counting subsequence patterns	$i+j=k$
Multiplying big integers	$i+j=k$ with carries
Counting XOR pairs	$i\oplus j=k$
Counting AND/OR pairs	$i\&j=k$ / $i\mid j=k$
Counting gcd pairs	$\gcd (i,j)=k$ — a Dirichlet convolution

Which transform

Combining rule	Transform	Cost
$i+j=k$	FFT / NTT	$O(n\log n)$
$i+j=k(\mathrm{mod}n)$ (cyclic)	FFT of length exactly $n$	$O(n\log n)$
$i\oplus j=k$	FWHT	$O(n\log n)$
$i\mid j=k$ (OR)	subset-sum zeta/Möbius	$O(n\log n)$
$i\&j=k$ (AND)	superset-sum zeta/Möbius	$O(n\log n)$
$i\cup j=k$, disjoint	subset convolution (ranked SOS)	$O(2^n{n}^2)$
$ij=k$	Dirichlet convolution	$O(n\log n)$
$\max (i,j)=k$	prefix sums	$O(n)$
$i+j=k$, max-plus, convex inputs	Minkowski sum	$O(n+m)$
$i+j=k$, max-plus, general	no known subquadratic algorithm	$O(n^2)$

The transform-based ones all share the same three-step shape:

transform(a);  transform(b);
for i: c[i] = a[i] * b[i];
inverse_transform(c);

Only the transform differs. That structural uniformity is worth internalising.

The FFT route

vector<long long> multiply(vector<long long> a, vector<long long> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n); fb.resize(n);
    fft(fa, false); fft(fb, false);
    for (int i = 0; i < n; i++) fa[i] *= fb[i];
    fft(fa, true);
    vector<long long> res(need);
    for (int i = 0; i < need; i++) res[i] = llround(fa[i].real());
    return res;
}

Pad to a power of two at least $|a|+|b|-1$; padding to less causes cyclic wraparound.

Precision and modulus

Situation	Method
Small integer coefficients, exact needed	NTT mod 998244353
Answer mod an arbitrary prime	3 NTT primes + CRT, or splitting
Real coefficients	complex FFT
Large integers, no modulus	split each coefficient into 15-bit halves; 4 transforms
Two real sequences at once	pack them as real and imaginary parts — halves the work

double FFT precision

Error grows roughly as $\log n\cdot \max |a|\cdot \max |b|$. With $n=10^6$ and coefficients up to $10^9$, plain complex FFT loses the low bits. Use NTT, or split coefficients.

Convolution without a transform

Sometimes the structure makes it cheap:

• Sparse inputs — if $a$ has $s$ non-zeros, direct evaluation is $O(sn)$, better than FFT when $s$ is small.
• Short inputs — below $n\approx 64$, the $O(n^2)$ loop beats FFT’s constant factor.
• Convex max-plus — merge the difference sequences in $O(n+m)$.
• One input is a prefix/suffix pattern — prefix sums suffice.

Multi-dimensional convolution

Transform along each axis in turn. A 2D convolution of an $n\times m$ grid is $O(nm\log (nm))$ — used for image filtering and for counting 2D patterns.

The general lesson

Convolution is the bridge between counting problems and fast algorithms. When a problem says “count the ways to combine one thing from each of two sets”, write down the generating function; the answer is a coefficient of a product, and the product is a convolution.

See Generating Functions for the counting side and FFT and NTT for the computation.

See also: FFT and NTT · FWHT · SOS DP