Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 63 ยท Math for Contests

FFT and NTT for Contests

Multiply polynomials and count pairs by sum in contests: a fast big-integer packing trick for exact results, plus an NTT modulo 998244353, tested against brute force.

A convolution takes two lists a and b and produces a list c where c[k] is the sum of a[i] * b[j] over all pairs with i + j = k. That is the same as multiplying the polynomials whose coefficients are a and b. Convolutions hide in many contest problems: "how many pairs of numbers add up to each possible sum?", "how many ways can k dice show a total of s?", matching with wildcards, and counting walks of a given length in some structured graphs.

Doing it with two loops costs O(n m). The Fast Fourier Transform makes it O(n log n), and the Number Theoretic Transform (NTT) does the same in exact modular arithmetic. This lesson is the contest view: how to recognize the problem, and two ways to code the product in Python.

Recognizing a convolution

Look for a sum of products whose indices add up to a constant. These are typical disguises:

Problem sentence Polynomials
Count pairs (i, j) with x[i] + y[j] = s Indicator polynomials: A(t) = sum of t^x[i], B(t) = sum of t^y[j]
Number of ways to make total s from k dice (t + t^2 + ... + t^6)^k
Does any pair of marked positions sum to s? Same indicator polynomials, check whether coefficient s is positive
Multiply two 10^5-digit numbers Digits as coefficients, then carry
Count matches of a pattern with ? wildcards Sum of three convolutions of character codes

If the sum is over a difference i - j = k, reverse one array first, and the indices add up again.

flowchart LR
    A["list a"] --> P["pack / transform"]
    B["list b"] --> Q["pack / transform"]
    P --> M["pointwise or big-integer multiply"]
    Q --> M
    M --> U["unpack / inverse transform"]
    U --> C["list c, c[k] = sum of a[i] * b[k - i]"]

Both techniques multiply in a new representation and convert back.

Trick 1: pack the coefficients into one huge integer

Python has arbitrary-precision integers with a fast (Karatsuba) multiplication written in C. That gives a surprisingly strong convolution without any transform: write each coefficient in a fixed-width slot of an integer, multiply the two integers, and read the slots of the product.

If a = [1, 2, 3], think of the number 1 + 2 * X + 3 * X^2 with X = 2^w. Multiplying two such numbers multiplies the polynomials, as long as no slot overflows into its neighbor. A result coefficient is at most min(len(a), len(b)) * max(a) * max(b), so pick the slot width w large enough for that bound. Then the product is the exact convolution with no rounding errors, which is the main advantage over floating-point FFT.

To pack efficiently, do not add shifted integers in a loop, which would be O(n^2). Instead turn every coefficient into a fixed number of bytes and let int.from_bytes build the big integer in one go. Unpacking works the same way with to_bytes.

Python Exact convolution by big-integer packing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The test uses 30,000 coefficients each, about 9 * 10^8 products for the naive method, and finishes in a moment. Checking three coefficients against direct sums is enough to catch a slot that is too narrow.

Packing is excellent when coefficients are exact counts. Its limits: memory (the packed integer has n * w bits, so for n = 10^6 and 64-bit slots it is 8 MB, which is still fine), and speed for the largest inputs, since Karatsuba is O(n^1.58), not O(n log n).

Trick 2: the NTT modulo 998244353

Many problems ask for the answer modulo a prime, typically 998244353. This prime is chosen because 998244353 - 1 = 119 * 2^23, so it has principal roots of unity of order 2^k for k up to 23. That is exactly what the FFT needs, but in integers: no floating-point error, ever.

The NTT works like the FFT:

  1. Pad both lists with zeros to a power of two that is at least len(a) + len(b) - 1.
  2. Transform both lists with ntt (evaluate the polynomials at the roots of unity).
  3. Multiply pointwise, modulo the prime.
  4. Transform back with the inverse (the same loop with the inverse root, then divide by n).

The implementation below is the standard iterative one: a bit-reversal permutation, then log2(n) rounds of butterflies. It checks itself against the naive loops, then solves a dice-counting task by raising a polynomial to the fourth power with repeated convolutions.

Python NTT convolution mod 998244353 and counting dice rolls

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pure Python NTT is slow: a transform of size 2^17 takes seconds. In a contest that allows only CPython you usually prefer packing (when the answer fits exact arithmetic) or the packing trick with a final % mod. In C++ the same code is a few dozen lines and fast enough for 10^6 elements.

Which one should you use?

Situation Method
Exact counts, moderate size, Python Packing (trick 1)
Answer wanted modulo 998244353, C++ NTT
Answer modulo another prime or a non-prime Pack exactly, then reduce each coefficient % mod (exact result first, so the modulus does not matter)
Floating-point result needed FFT with complex numbers (watch precision above about 10^14)

For modulus 10^9 + 7 the NTT does not apply directly, because that prime has no large power-of-two root of unity. Compute the exact convolution (or three NTT runs with different primes and combine them by the Chinese Remainder Theorem) and reduce at the end. Packing does this for free.

Pitfalls

  • Result length. The product of lists of lengths n and m has n + m - 1 coefficients. Trim the padding.
  • Slot width. A slot that is too small silently corrupts neighbors. Always use the true bound and test against a brute force on small data.
  • Indices that subtract. For i - j = k, reverse one list; for "pairs with i < j" subtract the diagonal i = j and halve.
  • Counting a pair with itself. In a[i] + a[j] = s using the same list for both sides, the products include (i, i) and both orders (i, j), (j, i). Subtract the cases with i = j and divide by two for unordered pairs.
  • Huge coefficients. An FFT with floats fails when the result exceeds about 10^14. Use NTT or exact packing instead.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the packing trick, what is the safe slot width?

    A result coefficient is at most min(len) * max(a) * max(b). If a slot is narrower than that, carries corrupt the next slot.
  2. 2. Why is 998244353 popular for NTT problems?

    998244353 = 119 * 2^23 + 1, so cyclic transforms of any power-of-two size up to 2^23 exist in its field.
  3. 3. How do you count pairs (i, j) with x[i] + y[j] = s for all s at once?

    The coefficient of t^s in A(t) * B(t) is the number of pairs whose values add up to s.
  4. 4. How many coefficients does the product of polynomials with 100 and 50 coefficients have?

    The degrees add: 99 + 49 = 148, so there are 149 coefficients, which is n + m - 1.

Summary

  • A convolution c[k] = sum of a[i] * b[k - i] is a polynomial product; spot it wherever indices add up to a constant.
  • Packing coefficients into fixed-width slots of a Python integer gives an exact convolution in one multiplication.
  • The NTT modulo 998244353 gives exact modular convolution in O(n log n); it needs a prime with a large power-of-two factor in p - 1.
  • For other moduli, compute exactly and reduce, or combine several primes with the Chinese Remainder Theorem.
  • Size the result as n + m - 1, size slots by the true bound, and test against naive loops.

Next: Geometry Toolkit for Contests