FFT and NTT

Evaluate a polynomial at $n$ roots of unity, multiply pointwise, interpolate back — turning $O(n^2)$ convolution into $O(n\log n)$.

The three steps

evaluate  A and B at the n-th roots of unity     O(n log n)
multiply  pointwise                              O(n)
interpolate (inverse transform)                  O(n log n)

Evaluation and interpolation are the same algorithm with $\omega$ replaced by ${\omega }^{-1}$ and a final division by $n$. See Cooley-Tukey for the derivation.

NTT — the one to use

Over ${\mathbb{Z}}_p$ with $p=c\cdot 2^k+1$, a primitive root $g$ gives a $2^k$-th root of unity $g^{(p-1)/2^k}$. Everything is exact integer arithmetic — no precision worries at all.

const long long MOD = 998244353, ROOT = 3;          // 998244353 = 119 * 2^23 + 1
 
void ntt(vector<long long>& a, bool invert) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        long long w = powmod(ROOT, (MOD - 1) / len, MOD);
        if (invert) w = powmod(w, MOD - 2, MOD);
        for (int i = 0; i < n; i += len) {
            long long wn = 1;
            for (int j = 0; j < len / 2; j++) {
                long long u = a[i+j], v = a[i+j+len/2] * wn % MOD;
                a[i+j]           = (u + v) % MOD;
                a[i+j+len/2]     = (u - v + MOD) % MOD;
                wn = wn * w % MOD;
            }
        }
    }
    if (invert) {
        long long ninv = powmod(n, MOD - 2, MOD);
        for (auto& x : a) x = x * ninv % MOD;
    }
}

Identical in shape to the complex FFT — only the root of unity changes.

NTT-friendly primes

Prime	Factorisation	Max length	Root
998244353	$119\cdot 2^{23}+1$	$2^{23}$	3
1004535809	$479\cdot 2^{21}+1$	$2^{21}$	3
469762049	$7\cdot 2^{26}+1$	$2^{26}$	3
2013265921	$15\cdot 2^{27}+1$	$2^{27}$	31
4179340454199820289	$29\cdot 2^{57}+1$	$2^{57}$	3

$10^9+7$ is not NTT-friendly ($p-1=2\cdot 500000003$), which is why $998244353$ has become the standard contest modulus.

Arbitrary modulus

When the required modulus is not NTT-friendly:

1. Three primes + CRT. Run NTT modulo three of the primes above; the true product is below $\prod p_i$, so CRT reconstructs it exactly, then reduce.
2. Coefficient splitting. Write $a_i=a_i^{hi}\cdot 2^{15}+a_i^{lo}$, similarly for $b$; four complex FFTs (or three with packing) give the exact product.
3. __int128 accumulation for small $n$.

Method 1 is the more robust; method 2 avoids modular arithmetic entirely.

FFT vs NTT

	Complex FFT	NTT
Arithmetic	double	integers mod $p$
Exactness	approximate	exact
Precision limits	real, and easy to hit	none
Speed	comparable	slightly slower per butterfly
Modulus required	no	yes (or CRT)
Real-valued inputs	natural	needs a modulus

Use NTT unless the coefficients are genuinely real.

Optimisations worth having

• Precompute the roots once into an array; recomputing powmod per level is a large constant.
• Avoid the modulo by using unsigned long long and reducing lazily (Barrett or Montgomery).
• Skip the final inverse transform when you only need one coefficient.
• Reuse transforms — squaring needs one forward transform, not two.
• Pack two real sequences into one complex FFT (real in the real part, the other in the imaginary part).

What builds on it

Operation	Cost
Polynomial multiplication	$O(n\log n)$
Series inverse, log, exp, sqrt, pow	$O(n\log n)$
Polynomial division and remainder	$O(n\log n)$
Multipoint evaluation and interpolation	$O(n{\log }^{2}n)$
GCD of polynomials	$O(n{\log }^{2}n)$ (half-GCD)
Linear recurrence, $n$-th term	$O(k\log k\log n)$
Big integer multiplication	$O(n\log n)$
String matching with wildcards	$O(n\log n)$
Counting with generating functions	$O(n\log n)$

See also: NTT · Cooley-Tukey · Convolution