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

> Master polynomial multiplication with Fourier Transforms in competitive programming. Learn how FFT speeds up calculations from O(n^2) to O(n log n) with this guide.

- Repository: [hzwer/shareoi](https://github.com/hzwer/shareoi)
- Tags: tutorial
- Published: 2026-03-03

---

**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$.

```cpp
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>>`.

```cpp
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.

```cpp
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.

```cpp
#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](https://github.com/hzwer/shareoi/blob/master/%E6%95%B0%E5%AD%A6/Fourier%20transform_%E9%83%AD%E6%99%93%E6%9C%A8.pdf) |
| Number theory | `数学/数论_杨定澄.pdf` | Covers primitive roots & modular arithmetic, prerequisites for NTT. | [📄 PDF](https://github.com/hzwer/shareoi/blob/master/%E6%95%B0%E5%AD%A6/%E6%95%B0%E8%AE%BA_%E6%9D%8E%E5%AE%9A%E6%BE%84.pdf) |
| Polynomial & sums | `数学/多项式及求和_杜瑜皓.pptx` | Discusses polynomial identities and summation techniques that often lead to convolution problems. | [📽 PPTX](https://github.com/hzwer/shareoi/blob/master/%E6%95%B0%E5%AD%A6/%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%8F%8A%E6%B1%82%E5%92%8C_%E6%9D%9C%E7%91%9C%E7%85%A0.pptx) |
| General algorithm slides | `基础算法/搜索及其优化_杨志灿.pptx` | Provides context on when to apply FFT within larger algorithmic pipelines. | [📽 PPTX](https://github.com/hzwer/shareoi/blob/master/%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95/%E6%90%9C%E7%B4%A2%E5%8F%8A%E5%85%B6%E4%BC%98%E5%8C%96_%E6%9D%A8%E5%BF%97%E7%81%AF.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$.