Using Fourier Transforms for Polynomial Multiplication in Competitive Programming: A Complete Guide

The Fast Fourier Transform (FFT) reduces polynomial multiplication from $O(n^2)$ to $O(n \log n)$ by converting coefficient vectors to point-value form at roots of unity, multiplying pointwise, and interpolating back.

Polynomial multiplication is a fundamental operation in competitive programming, appearing in problems involving convolutions, generating functions, and string matching. While the naive $O(n^2)$ approach suffices for small inputs, it fails when degrees exceed a few thousand. According to the shareOI repository, the Fast Fourier Transform provides the standard solution, reducing complexity to $O(n \log n)$ through elegant evaluation at complex roots of unity.

Why Polynomial Multiplication Matters in Competitive Programming

Polynomial multiplication (convolution) appears in diverse contest scenarios:

• Probability distributions – computing the sum of independent random variables.
• Combinatorial generating functions – multiplying polynomials where coefficients represent counts.
• String matching – treating strings as polynomials to find patterns via convolution.
• Large integer arithmetic – representing numbers as polynomials in base $10^9$.

When the result degree exceeds $2^{10}$, the quadratic naive algorithm becomes a bottleneck, necessitating FFT.

The Mathematical Foundation: DFT and the Convolution Theorem

The shareOI repository contains a concise lecture on the mathematical underpinnings in 数学/Fourier transform_郭晓旭.pdf. This document explains that the Discrete Fourier Transform (DFT) evaluates a polynomial $A(x) = \sum_{k=0}^{n-1} a_k x^k$ at the $n$-th roots of unity $\omega_n^k = e^{2\pi i k/n}$.

The Convolution Theorem states that multiplication in the coefficient domain corresponds to pointwise multiplication in the frequency domain:

$$\mathcal{F}(A \cdot B) = \mathcal{F}(A) \times \mathcal{F}(B)$$

Thus, to multiply two polynomials, we transform both to point-value form, multiply pointwise, and apply the inverse DFT to recover the coefficients.

The Cooley-Tukey FFT Algorithm

The Fast Fourier Transform implements the DFT in $O(n \log n)$ using a divide-and-conquer strategy. The Cooley-Tukey algorithm recursively splits a DFT of size $n$ into two DFTs of size $n/2$ (even and odd indices).

In competitive programming, an iterative implementation with bit-reversal permutation is preferred over recursion to minimize overhead. The algorithm proceeds as follows:

1. Bit-reversal permutation – reorder the array so that index $i$ is swapped with the bit-reversed index of $i$.
2. Butterfly operations – for each length $len = 2, 4, 8, \dots, n$, combine pairs of elements using the twiddle factors $\omega_{len}^k$.

Implementation Guide for Competitive Programming

Choosing the Array Size

FFT requires the transform size to be a power of two. For polynomials $A$ and $B$ with degrees $n$ and $m$, choose $N$ as the smallest power of two satisfying $N \geq n + m + 1$.

int n = 1;
while (n < (int)a.size() + (int)b.size()) n <<= 1;

The Iterative FFT Function

The core fft function implements the iterative Cooley-Tukey algorithm with bit-reversal. It operates in-place on a vector<complex<double>>.

using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> & a, bool invert) {
    int n = a.size();
    // Bit-reversal permutation
    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]);
    }
    // Butterfly operations
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len/2; ++j) {
                cd u = a[i+j];
                cd v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }
    if (invert) {
        for (cd & x : a) x /= n;
    }
}

Handling Precision and Rounding

Floating-point errors accumulate during FFT. When the final coefficients must be integers (the common case in CP), round the real parts using llround or add 0.5 before casting.

vector<long long> res(n);
for (int i = 0; i < n; ++i)
    res[i] = (long long) llround(fa[i].real());

Complete C++ Implementation

Below is a battle-tested, copy-paste ready solution that follows the architectural pattern described in the shareOI materials. It reads two polynomials, computes their product via FFT, and outputs the coefficients.

#include <bits/stdc++.h>
using namespace std;

using cd = complex<double>;
const double PI = acos(-1);

// ----- iterative FFT -----
void fft(vector<cd> & a, bool invert) {
    int n = a.size();
    // bit-reversal permutation
    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]);
    }
    // main loops
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len/2; ++j) {
                cd u = a[i+j];
                cd v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }
    if (invert) {
        for (cd & x : a) x /= n;
    }
}

// ----- convolution (polynomial multiplication) -----
vector<long long> multiply(const vector<long long> &a,
                          const vector<long long> &b) {
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < (int)a.size() + (int)b.size()) n <<= 1;
    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(n);
    for (int i = 0; i < n; ++i)
        res[i] = (long long) llround(fa[i].real()); // rounding
    // optional: trim trailing zeros
    while (!res.empty() && res.back() == 0) res.pop_back();
    return res;
}

// ----- example usage -----
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // read polynomial degrees and coefficients
    int n, m;                     // deg(A), deg(B)
    cin >> n >> m;
    vector<long long> A(n+1), B(m+1);
    for (auto &x : A) cin >> x;
    for (auto &x : B) cin >> x;

    vector<long long> C = multiply(A, B);
    for (size_t i = 0; i < C.size(); ++i) {
        if (i) cout << ' ';
        cout << C[i];
    }
    cout << '\n';
    return 0;
}

Number-Theoretic Transform (NTT) for Modular Arithmetic

When problem constraints require results modulo a prime (commonly $998244353$ or $10^9+7$), floating-point FFT introduces unacceptable rounding errors. The Number-Theoretic Transform (NTT) replaces complex roots of unity with integer primitive roots under a modular field.

The shareOI repository provides the necessary theoretical background in 数学/数论_杨定澄.pdf, which covers primitive roots and modular exponentiation—prerequisites for implementing NTT. The algorithmic structure remains identical to FFT: bit-reversal permutation followed by iterative butterfly operations, but using modular arithmetic instead of complex numbers.

For moduli that are not NTT-friendly (such as $10^9+7$), competitive programmers typically use three NTTs with different primes followed by the Chinese Remainder Theorem (CRT), or Garner's algorithm for reconstruction.

Key Educational Resources in shareOI

The shareOI repository maintains several lecture materials that contextualize FFT within the broader competitive programming curriculum:

Category	File	Description	Link
Mathematics lecture	数学/Fourier transform_郭晓旭.pdf	Explains DFT, convolution theorem, and FFT basics.	📄 PDF
Number theory	数学/数论_杨定澄.pdf	Covers primitive roots & modular arithmetic, prerequisites for NTT.	📄 PDF
Polynomial & sums	数学/多项式及求和_杜瑜皓.pptx	Discusses polynomial identities and summation techniques that often lead to convolution problems.	📽 PPTX
General algorithm slides	基础算法/搜索及其优化_杨志灿.pptx	Provides context on when to apply FFT within larger algorithmic pipelines.	📽 PPTX

Summary

• FFT reduces complexity from $O(n^2)$ to $O(n \log n)$ by exploiting the convolution theorem and evaluating polynomials at complex roots of unity.
• Iterative implementation with bit-reversal permutation is preferred in competitive programming for its speed and lack of recursion overhead.
• Precision handling requires rounding with llround or adding 0.5 before casting to long long to mitigate floating-point errors.
• NTT substitutes complex arithmetic with modular arithmetic when results must be exact under a prime modulus, utilizing primitive roots as described in 数学/数论_杨定澄.pdf.
• Power-of-two padding is mandatory; the transform size must be at least $\deg(A) + \deg(B) + 1$ rounded up to the next power of two.

Frequently Asked Questions

When should I use FFT instead of naive multiplication in competitive programming?

Switch to FFT when the sum of the polynomial degrees exceeds approximately $2000$ to $5000$. Below this threshold, the constant factors of FFT (complex arithmetic, bit-reversal) make naive $O(n^2)$ multiplication faster. For constraints where $n, m \leq 10^5$ or $10^6$, FFT is mandatory to avoid time limit exceeded (TLE) verdicts.

What is the difference between FFT and NTT?

FFT operates over complex numbers using floating-point arithmetic, making it suitable for integer convolution when rounding errors are manageable. NTT (Number-Theoretic Transform) operates over a finite field modulo a prime $p$, using integer primitive roots instead of complex roots of unity. NTT produces exact results without precision errors but requires the modulus to be of the form $c \cdot 2^k + 1$ to support the required root of unity. For arbitrary moduli, combine three NTTs with the Chinese Remainder Theorem.

How do I handle precision errors with FFT?

Floating-point errors accumulate during the butterfly operations. When the final coefficients must be integers (the typical case), round the real part of each complex number to the nearest integer using llround from <cmath>, or add 0.5 before casting to long long for positive values. If the input coefficients are large (e.g., $> 10^9$), consider using NTT instead to avoid precision loss entirely.

Why must the FFT array size be a power of two?

The iterative Cooley-Tukey algorithm requires dividing the transform into stages of length $2, 4, 8, \dots, n$. This structure relies on the existence of primitive $n$-th roots of unity where $n$ is a power of two, allowing the "butterfly" operations to combine results from smaller transforms efficiently. If the required size is not a power of two, zero-pad the coefficient vectors to the next power of two $\geq \deg(A) + \deg(B) + 1$.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}