SyntaxPilot
Courses/Competitive Programming/Lesson 82
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 82 of 90

FFT and polynomial multiplication

queued

These are the notes for Competitive Programming episode 82. The fast Fourier transform (FFT) multiplies two polynomials with N coefficients in O(N log N) instead of O(N²). Lunch Combos counts, for every total price, the combos of one main and one drink: every pair is 4·10^10 steps (TLE), but the counts are the coefficients of a polynomial product (a convolution), and the FFT computes it in a fraction of a second. A real bug: casting the FFT's doubles with (ll) instead of llround turns a true 1 (which came back as 0.99999999999999989) into 0. Huge Product multiplies two 300,000-digit numbers: the schoolbook method is 9·10^10 digit products (TLE); the FFT on the digit lists plus carries takes about a third of a second, and a second real bug prints 000000 for 0 × 31415. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

Long multiplication by hand is a convolution. Multiply 123 by 45 on paper, writing the digits lowest first: 123 is (3, 2, 1) and 45 is (5, 4). Digit i of the first number times digit j of the second lands in column i + j, exactly like x^i · x^j = x^(i+j). Before carrying, the columns hold:

Column Products that land there Sum
0 (units) 3·5 15
1 (tens) 3·4 + 2·5 22
2 (hundreds) 2·4 + 1·5 13
3 (thousands) 1·4 4

Each column is a sum of products whose positions add up to the column number: c[k] = Σ a[i] · b[k − i]. That is a convolution. Then the carries: 15 → write 5, carry 1; 22 + 1 = 23 → 3, carry 2; 13 + 2 = 15 → 5, carry 1; 4 + 1 = 5. The product is 5535.

The marks on a clock face are roots of unity. Put 8 marks round a clock, every 45 degrees. As complex numbers on the unit circle, they are the 8th roots of unity: raise any of them to the 8th power and you get 1. Squaring a point on the unit circle doubles its angle, so the 8 marks land on only 4 (0°, 90°, 180°, 270°), because opposite marks land on the same place: 45° and 225° both go to 90°. That halving is the whole trick of the FFT.

Problem F1 · Lunch Combos

(Written for this course.)

  • Shop A sells n mains and shop B sells m drinks, n, m ≤ 2·10^5.
  • Every price is an integer from 1 to 2·10^5.
  • A combo is one main plus one drink.
  • For every total s from 2 up to (the most expensive main + the most expensive drink), print how many combos cost exactly s.
4 3
1 2 3 5
2 4 4

Expected: 0 1 1 3 2 3 0 2 (totals 2 to 9). Total 5 has three combos: 1 + 4 (twice, there are two drinks at 4) and 3 + 2.

There can be n · m = 4·10^10 combos: far too many to list one by one.

Attempt 1: every pair

For every main and every drink, add one to the count of their total.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (auto& v : a) cin >> v;
    for (auto& v : b) cin >> v;
    vector<ll> c(*max_element(a.begin(), a.end()) + *max_element(b.begin(), b.end()) + 1);
    for (int x : a)
        for (int y : b) c[x + y]++;                  // every pair
    for (int s = 2; s < (int)c.size(); s++) cout << c[s] << " ";
}
0 1 1 3 2 3 0 2

Correct. Now 200000 mains and 200000 drinks with random prices (mt19937 gen(82)), printing only the most popular total and its count:

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

int main() {
    mt19937 gen(82);
    int n = 200000, m = 200000;                     // 200000 mains, 200000 drinks
    vector<int> a(n), b(m);
    for (auto& v : a) v = gen() % 200000 + 1;
    for (auto& v : b) v = gen() % 200000 + 1;
    vector<ll> c(*max_element(a.begin(), a.end()) + *max_element(b.begin(), b.end()) + 1);
    for (int x : a)
        for (int y : b) c[x + y]++;                  // every pair
    int best = max_element(c.begin(), c.end()) - c.begin();
    cout << best << " " << c[best] << "\n";        // the most popular total
}

4·10^10 pair updates: Time Limit Exceeded in the SyntaxPilot compiler (here it was still running when stopped after 10 seconds).

Count by price: a convolution

First count how many items have each price: A[i] = mains at price i, B[j] = drinks at price j. On the sample, A = (0, 1, 1, 1, 0, 1) for prices 0 to 5 and B = (0, 0, 1, 0, 2) for prices 0 to 4. Then

combos[s] = Σ A[i] · B[s − i]

Total 5: price 1 with price 4 is 1 · 2 = 2 combos, plus price 3 with price 2 is 1 · 1 = 1: three combos. This is exactly the column sum of long multiplication. Write shop A as the polynomial A(x) = Σ A[i] x^i and shop B the same way: the coefficient of x^s in A(x) · B(x) is the number of combos costing s.

There are only 2·10^5 prices, not 4·10^10 pairs, but computed directly the convolution is still prices × prices: O(V²) = 4·10^10. We need a faster way to multiply polynomials.

Two ways to describe a polynomial

  • Coefficient representation: the list of coefficients (a0, a1, …, a(N−1)). Multiplying two such lists directly is a convolution: O(N²).
  • Value representation: the values A(x0), A(x1), …, A(x(N−1)) at N chosen points. Two points decide a line; in the same way, N values decide a polynomial with N coefficients (degree < N).

With values, multiplying is easy: at any point x, C(x) = A(x) · B(x), so the product's values are just N multiplications: O(N).

The plan:

  1. Evaluation: coefficients → values (for both A and B).
  2. Multiply the values point by point.
  3. Interpolation: values → coefficients.

The catch: evaluating a polynomial at N ordinary points costs N · N again. Unless we choose the points very cleverly.

Complex roots of unity

A complex number is a + bi with i² = −1; it is a point in the plane. On the unit circle, e^(iθ) = cos θ + i sin θ is the point at angle θ, and multiplying two such points adds their angles.

The N-th roots of unity are the N points evenly spaced round the unit circle: w^0, w^1, …, w^(N−1) with w = e^(2πi/N) (one N-th of a full turn). Each one satisfies (w^k)^N = 1. Two facts make them special:

  • Squaring halves them: (w^k)² = w^(2k) is an (N/2)-th root of unity, so the squares of the N roots take only N/2 different values.
  • Opposites pair up: w^(k + N/2) = −w^k (half a turn further is the opposite point).

The even/odd split

Split A into its even-position and odd-position coefficients:

  • E(y) = a0 + a2·y + a4·y² + …
  • O(y) = a1 + a3·y + a5·y² + …

Then A(x) = E(x²) + x · O(x²). At the N roots of unity, x² takes only N/2 values (the (N/2)-th roots), so we only need E and O at the N/2 roots: two problems of half the size. Then for k < N/2:

  • A(w^k) = E(w^2k) + w^k · O(w^2k)
  • A(w^(k + N/2)) = E(w^2k) − w^k · O(w^2k)

One multiplication w^k · O gives two answers. This pair (u + v, u − v with v = w·O) is called a butterfly.

Half, half, half: T(N) = 2 T(N/2) + O(N), so log₂ N levels each costing N: O(N log N). Every level halves the size exactly, which is why N must be a power of two. This is the Cooley-Tukey FFT (1965). Computing all N values A(w^k) is called the discrete Fourier transform (DFT); the FFT is the fast algorithm that computes it.

The inverse FFT

Going back from values to coefficients is the same transform with the roots turned the other way (w⁻¹ = e^(−2πi/N) instead of w), then dividing every result by N. Why: applying the forward and then the backward transform sums w^(jk) over all k, and that sum is N when j ≡ 0 (mod N) and 0 otherwise (the points of a regular polygon cancel out). In the code it is one flag: ang changes sign and x /= n at the end.

So multiplying two polynomials is 3 FFTs + N products: O(N log N).

Bit-reversal: the FFT without recursion

The recursion keeps splitting by even and odd positions. If you follow where a coefficient ends up at the bottom of the recursion, its index is its original index with the bits reversed. For N = 8:

Index Binary Reversed Position
0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 011 3
7 111 111 7

So the contest version first reorders the array to 0 4 2 6 1 5 3 7 (swap a[i] and a[j] when j is i bit-reversed and i < j; the j loop is "add 1 starting from the top bit"). Then it merges neighbours in place, level by level: blocks of length 2, then 4, then 8, … For each block, w[k] = polar(1.0, ang * k) are the roots of that level, and the inner loop is the butterfly a[i + k] = u + v, a[i + k + len/2] = u − v.

Why N is a power of two ≥ a.size() + b.size() − 1

The product of a polynomial with a.size() coefficients and one with b.size() coefficients has a.size() + b.size() − 1 coefficients (degrees add). N values only decide a polynomial with fewer than N coefficients, so N must be at least that size, and a power of two for the halving. If N is too small, the FFT computes a cyclic convolution: coefficient k lands at k mod N, so high totals wrap round and get added to low ones (a real demo is in Common mistakes). Extra zero coefficients (resize(n)) are harmless.

Attempt 2: the FFT, with a rounding bug

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

using cd = complex<double>;

void fft(vector<cd>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // reorder: bit-reversed indices
        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) {        // merge halves: len/2 -> len
        double ang = 2 * M_PI / len * (inv ? -1 : 1);
        vector<cd> w(len / 2);
        for (int k = 0; k < len / 2; k++) w[k] = polar(1.0, ang * k);   // roots of unity
        for (int i = 0; i < n; i += len)
            for (int k = 0; k < len / 2; k++) {
                cd u = a[i + k], v = a[i + k + len / 2] * w[k];
                a[i + k] = u + v;                   // E + w O
                a[i + k + len / 2] = u - v;         // E - w O
            }
    }
    if (inv) for (auto& x : a) x /= n;
}

vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;                      // a power of two, big enough
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n);
    fb.resize(n);
    fft(fa, false);
    fft(fb, false);                                 // coefficients -> values
    for (int i = 0; i < n; i++) fa[i] *= fb[i];      // multiply the values
    fft(fa, true);                                  // values -> coefficients
    vector<ll> r(need);
    for (int i = 0; i < need; i++) r[i] = (ll)fa[i].real();
    return r;
}

vector<ll> counts(const vector<int>& a) {           // cnt[v] = items that cost v
    vector<ll> cnt(*max_element(a.begin(), a.end()) + 1);
    for (int v : a) cnt[v]++;
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (auto& v : a) cin >> v;
    for (auto& v : b) cin >> v;
    vector<ll> c = multiply(counts(a), counts(b));
    for (int s = 2; s < (int)c.size(); s++) cout << c[s] << " ";
}
0 0 0 3 2 3 0 2

Wrong Answer: totals 3 and 4 should have one combo each. Adding one line, cerr << setprecision(17) << i << " " << fa[i].real() << "\n";, next to the cast prints each total i with its raw double, and shows why:

0 5.5511151231257827e-17
1 0
2 1.6258839764163448e-17
3 0.99999999999999989
4 0.99999999999999989
5 3
6 2
7 3
8 0
9 2

The FFT works in doubles, so every result has a tiny error. The true 1 came back as 0.99999999999999989, and casting to long long truncates towards zero: 0. Round to the nearest integer instead.

The fix: llround

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

using cd = complex<double>;

void fft(vector<cd>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // reorder: bit-reversed indices
        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) {        // merge halves: len/2 -> len
        double ang = 2 * M_PI / len * (inv ? -1 : 1);
        vector<cd> w(len / 2);
        for (int k = 0; k < len / 2; k++) w[k] = polar(1.0, ang * k);   // roots of unity
        for (int i = 0; i < n; i += len)
            for (int k = 0; k < len / 2; k++) {
                cd u = a[i + k], v = a[i + k + len / 2] * w[k];
                a[i + k] = u + v;                   // E + w O
                a[i + k + len / 2] = u - v;         // E - w O
            }
    }
    if (inv) for (auto& x : a) x /= n;
}

vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;                      // a power of two, big enough
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n);
    fb.resize(n);
    fft(fa, false);
    fft(fb, false);                                 // coefficients -> values
    for (int i = 0; i < n; i++) fa[i] *= fb[i];      // multiply the values
    fft(fa, true);                                  // values -> coefficients
    vector<ll> r(need);
    for (int i = 0; i < need; i++) r[i] = llround(fa[i].real());
    return r;
}

vector<ll> counts(const vector<int>& a) {           // cnt[v] = items that cost v
    vector<ll> cnt(*max_element(a.begin(), a.end()) + 1);
    for (int v : a) cnt[v]++;
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (auto& v : a) cin >> v;
    for (auto& v : b) cin >> v;
    vector<ll> c = multiply(counts(a), counts(b));
    for (int s = 2; s < (int)c.size(); s++) cout << c[s] << " ";
}
0 1 1 3 2 3 0 2

The same as the brute force. Edge case: one main and one drink, both costing 1:

1 1
1
1
1

1 combo at total 2. And 200000 of each, printing the most popular total and its number of combos:

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

using cd = complex<double>;

void fft(vector<cd>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // reorder: bit-reversed indices
        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) {        // merge halves: len/2 -> len
        double ang = 2 * M_PI / len * (inv ? -1 : 1);
        vector<cd> w(len / 2);
        for (int k = 0; k < len / 2; k++) w[k] = polar(1.0, ang * k);   // roots of unity
        for (int i = 0; i < n; i += len)
            for (int k = 0; k < len / 2; k++) {
                cd u = a[i + k], v = a[i + k + len / 2] * w[k];
                a[i + k] = u + v;                   // E + w O
                a[i + k + len / 2] = u - v;         // E - w O
            }
    }
    if (inv) for (auto& x : a) x /= n;
}

vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;                      // a power of two, big enough
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n);
    fb.resize(n);
    fft(fa, false);
    fft(fb, false);                                 // coefficients -> values
    for (int i = 0; i < n; i++) fa[i] *= fb[i];      // multiply the values
    fft(fa, true);                                  // values -> coefficients
    vector<ll> r(need);
    for (int i = 0; i < need; i++) r[i] = llround(fa[i].real());
    return r;
}

vector<ll> counts(const vector<int>& a) {           // cnt[v] = items that cost v
    vector<ll> cnt(*max_element(a.begin(), a.end()) + 1);
    for (int v : a) cnt[v]++;
    return cnt;
}

int main() {
    mt19937 gen(82);
    int n = 200000, m = 200000;                     // 200000 mains, 200000 drinks
    vector<int> a(n), b(m);
    for (auto& v : a) v = gen() % 200000 + 1;
    for (auto& v : b) v = gen() % 200000 + 1;
    vector<ll> c = multiply(counts(a), counts(b));
    int best = max_element(c.begin(), c.end()) - c.begin();
    cout << best << " " << c[best] << "\n";        // the most popular total
}
200105 201011

Total 200105 is the most popular, with 201011 combos. About 0.3 seconds instead of 4·10^10 steps.

Stress test

The FFT against the plain double loop, on 500 random polynomials with up to 60 coefficients up to 10^5:

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

using cd = complex<double>;

void fft(vector<cd>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // reorder: bit-reversed indices
        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) {        // merge halves: len/2 -> len
        double ang = 2 * M_PI / len * (inv ? -1 : 1);
        vector<cd> w(len / 2);
        for (int k = 0; k < len / 2; k++) w[k] = polar(1.0, ang * k);   // roots of unity
        for (int i = 0; i < n; i += len)
            for (int k = 0; k < len / 2; k++) {
                cd u = a[i + k], v = a[i + k + len / 2] * w[k];
                a[i + k] = u + v;                   // E + w O
                a[i + k + len / 2] = u - v;         // E - w O
            }
    }
    if (inv) for (auto& x : a) x /= n;
}

vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;                      // a power of two, big enough
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n);
    fb.resize(n);
    fft(fa, false);
    fft(fb, false);                                 // coefficients -> values
    for (int i = 0; i < n; i++) fa[i] *= fb[i];      // multiply the values
    fft(fa, true);                                  // values -> coefficients
    vector<ll> r(need);
    for (int i = 0; i < need; i++) r[i] = llround(fa[i].real());
    return r;
}

int main() {
    mt19937 gen(82);
    for (int it = 1; it <= 500; it++) {
        vector<ll> a(gen() % 60 + 1), b(gen() % 60 + 1);
        for (auto& v : a) v = gen() % 100000;
        for (auto& v : b) v = gen() % 100000;
        vector<ll> slow(a.size() + b.size() - 1);
        for (int i = 0; i < (int)a.size(); i++)
            for (int j = 0; j < (int)b.size(); j++) slow[i + j] += a[i] * b[j];
        if (slow != multiply(a, b)) { cout << "mismatch on test " << it; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem F2 · Huge Product

(Written for this course.)

  • Two non-negative integers with up to 3·10^5 digits each. Print their product.
12345678901234567890 98765432109876543210

Expected: 1219326311370217952237463801111263526900 (40 digits; Python's big integers give the same).

A number is a polynomial in disguise: 123 = 3 + 2x + x² at x = 10. So put the digits lowest first, multiply the digit lists with the FFT (the column sums of long multiplication), then do the carries exactly like on paper: c[i + 1] += c[i] / 10; c[i] %= 10. Before carrying, every column is at most 81 · 3·10^5 ≈ 2.4·10^7: doubles handle that with plenty of room.

Attempt 1: schoolbook multiplication (TLE)

Two random 300000-digit numbers (mt19937 gen(82), first digits 9), printing the number of digits and the first 15:

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

int main() {
    mt19937 gen(82);
    string x(300000, '0'), y(300000, '0');        // two 300000-digit numbers
    for (auto& d : x) d = '0' + gen() % 10;
    for (auto& d : y) d = '0' + gen() % 10;
    x[0] = y[0] = '9';
    vector<ll> c(x.size() + y.size());
    for (int i = 0; i < (int)x.size(); i++)
        for (int j = 0; j < (int)y.size(); j++)        // every digit pair
            c[i + j] += (x[x.size() - 1 - i] - '0') * (y[y.size() - 1 - j] - '0');
    for (int i = 0; i + 1 < (int)c.size(); i++) {   // carries, like on paper
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();   // no leading zeros
    cout << c.size() << " digits, starting ";
    for (int i = c.size() - 1; i >= (int)c.size() - 15; i--) cout << c[i];
    cout << "\n";
}

9·10^10 digit products: Time Limit Exceeded in the SyntaxPilot compiler (here it was still running when stopped after 10 seconds).

Attempt 2: FFT + carries, with a leading-zero bug

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

using cd = complex<double>;

void fft(vector<cd>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // reorder: bit-reversed indices
        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) {        // merge halves: len/2 -> len
        double ang = 2 * M_PI / len * (inv ? -1 : 1);
        vector<cd> w(len / 2);
        for (int k = 0; k < len / 2; k++) w[k] = polar(1.0, ang * k);   // roots of unity
        for (int i = 0; i < n; i += len)
            for (int k = 0; k < len / 2; k++) {
                cd u = a[i + k], v = a[i + k + len / 2] * w[k];
                a[i + k] = u + v;                   // E + w O
                a[i + k + len / 2] = u - v;         // E - w O
            }
    }
    if (inv) for (auto& x : a) x /= n;
}

vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;                      // a power of two, big enough
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n);
    fb.resize(n);
    fft(fa, false);
    fft(fb, false);                                 // coefficients -> values
    for (int i = 0; i < n; i++) fa[i] *= fb[i];      // multiply the values
    fft(fa, true);                                  // values -> coefficients
    vector<ll> r(need);
    for (int i = 0; i < need; i++) r[i] = llround(fa[i].real());
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string x, y;
    cin >> x >> y;
    vector<ll> a(x.size()), b(y.size());
    for (int i = 0; i < (int)x.size(); i++) a[i] = x[x.size() - 1 - i] - '0';   // lowest digit first
    for (int i = 0; i < (int)y.size(); i++) b[i] = y[y.size() - 1 - i] - '0';
    vector<ll> c = multiply(a, b);
    c.push_back(0);
    for (int i = 0; i + 1 < (int)c.size(); i++) {   // carries, like on paper
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
    cout << "\n";
}

Edge case first:

0 31415
000000

Six zeros: the product has 1 + 5 − 1 = 5 columns plus the extra carry column, all zero, and all of them are printed. The answer is just 0. Strip the leading zeros, but always keep at least one digit.

The fix: strip leading zeros

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

using cd = complex<double>;

void fft(vector<cd>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // reorder: bit-reversed indices
        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) {        // merge halves: len/2 -> len
        double ang = 2 * M_PI / len * (inv ? -1 : 1);
        vector<cd> w(len / 2);
        for (int k = 0; k < len / 2; k++) w[k] = polar(1.0, ang * k);   // roots of unity
        for (int i = 0; i < n; i += len)
            for (int k = 0; k < len / 2; k++) {
                cd u = a[i + k], v = a[i + k + len / 2] * w[k];
                a[i + k] = u + v;                   // E + w O
                a[i + k + len / 2] = u - v;         // E - w O
            }
    }
    if (inv) for (auto& x : a) x /= n;
}

vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;                      // a power of two, big enough
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n);
    fb.resize(n);
    fft(fa, false);
    fft(fb, false);                                 // coefficients -> values
    for (int i = 0; i < n; i++) fa[i] *= fb[i];      // multiply the values
    fft(fa, true);                                  // values -> coefficients
    vector<ll> r(need);
    for (int i = 0; i < need; i++) r[i] = llround(fa[i].real());
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string x, y;
    cin >> x >> y;
    vector<ll> a(x.size()), b(y.size());
    for (int i = 0; i < (int)x.size(); i++) a[i] = x[x.size() - 1 - i] - '0';   // lowest digit first
    for (int i = 0; i < (int)y.size(); i++) b[i] = y[y.size() - 1 - i] - '0';
    vector<ll> c = multiply(a, b);
    c.push_back(0);
    for (int i = 0; i + 1 < (int)c.size(); i++) {   // carries, like on paper
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();   // no leading zeros
    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
    cout << "\n";
}

0 31415:

0

The two 20-digit numbers, far beyond long long:

1219326311370217952237463801111263526900

The same 40 digits that Python's big integers give. The two random 300000-digit numbers:

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

using cd = complex<double>;

void fft(vector<cd>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // reorder: bit-reversed indices
        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) {        // merge halves: len/2 -> len
        double ang = 2 * M_PI / len * (inv ? -1 : 1);
        vector<cd> w(len / 2);
        for (int k = 0; k < len / 2; k++) w[k] = polar(1.0, ang * k);   // roots of unity
        for (int i = 0; i < n; i += len)
            for (int k = 0; k < len / 2; k++) {
                cd u = a[i + k], v = a[i + k + len / 2] * w[k];
                a[i + k] = u + v;                   // E + w O
                a[i + k + len / 2] = u - v;         // E - w O
            }
    }
    if (inv) for (auto& x : a) x /= n;
}

vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;                      // a power of two, big enough
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n);
    fb.resize(n);
    fft(fa, false);
    fft(fb, false);                                 // coefficients -> values
    for (int i = 0; i < n; i++) fa[i] *= fb[i];      // multiply the values
    fft(fa, true);                                  // values -> coefficients
    vector<ll> r(need);
    for (int i = 0; i < need; i++) r[i] = llround(fa[i].real());
    return r;
}

int main() {
    mt19937 gen(82);
    string x(300000, '0'), y(300000, '0');        // two 300000-digit numbers
    for (auto& d : x) d = '0' + gen() % 10;
    for (auto& d : y) d = '0' + gen() % 10;
    x[0] = y[0] = '9';
    vector<ll> a(x.size()), b(y.size());
    for (int i = 0; i < (int)x.size(); i++) a[i] = x[x.size() - 1 - i] - '0';   // lowest digit first
    for (int i = 0; i < (int)y.size(); i++) b[i] = y[y.size() - 1 - i] - '0';
    vector<ll> c = multiply(a, b);
    c.push_back(0);
    for (int i = 0; i + 1 < (int)c.size(); i++) {   // carries, like on paper
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();   // no leading zeros
    cout << c.size() << " digits, starting ";
    for (int i = c.size() - 1; i >= (int)c.size() - 15; i--) cout << c[i];
    cout << "\n";
}
600000 digits, starting 871993647191803

600000 digits in about a third of a second. I checked all 600000 digits against Python big integers too: they agree. (The first digits are 871993647191803 because both numbers start with a 9 followed by random digits.)

Precision limits of doubles

A double has a 53-bit mantissa: integers are exact only up to 2^53 ≈ 9·10^15, and the FFT adds rounding error that grows with N and with the size of the values. The results come back as integers plus a small error, and llround is correct only while that error stays below 0.5. Rules of thumb:

  • Lunch Combos: the counts are at most 2·10^5 per price, the FFT is N = 2^19: safe.
  • Huge Product: columns ≤ 2.4·10^7, N = 2^20: safe (and checked against Python on all 600000 digits).
  • Coefficients up to about 10^9, or results above about 10^14 to 10^15: not safe. Split each coefficient into two halves of about 15 bits, or use the NTT (number theoretic transform, next episode), which works modulo a prime such as 998244353 and is exact.

Complexity vs the constraints

Method Time Verdict
every combo (n = m = 2·10^5) O(n · m) = 4·10^10 TLE
schoolbook digits (3·10^5 each) O(n · m) = 9·10^10 TLE
count by price, then prices × prices O(V²) = 4·10^10 TLE
FFT multiply, Lunch Combos N = 2^19 (need = 400001): 3 FFTs × 19 levels × N/2 butterflies ≈ 1.5·10^7 accepted (~0.3 s)
FFT multiply, Huge Product N = 2^20 (need = 599999): about 10^7 butterflies per FFT accepted (~0.3 s)

Memory: O(N) complex numbers (16 bytes each): about 8 MB for N = 2^19. Counts of combos reach 4·10^10 in total: long long.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
(ll)fa[i].real() 0 0 0 3 2 3 0 2 on the sample 1 came back as 0.99999999999999989 and was truncated llround(fa[i].real())
size n < a.size() + b.size() − 1 size 4: 22 13 28 27 instead of 4 13 28 27 18 the FFT is cyclic: high coefficients wrap round n ≥ need, a power of two
printing every column 000000 for 0 31415 leading zeros pop zeros, keep one digit
huge coefficients in doubles wrong low digits 53-bit precision split the coefficients, or the NTT (next episode)
forgetting x /= n in the inverse every coefficient n times too big the inverse needs the division divide by n
digits in the order they are read a wrong product column i + j needs the lowest digit first reverse the digits
int for the counts overflow up to 4·10^10 combos long long

The wrap-around demo: the same fft and multiply as in Problem F1, plus a multiplyTooSmall whose size is only big enough for the inputs, not for the product. (1 + 2x + 3x²)(4 + 5x + 6x²) has 5 coefficients, but size 4 can only hold 4:

// #include, fft and multiply: exactly as in Problem F1 above

vector<ll> multiplyTooSmall(const vector<ll>& a, const vector<ll>& b) {
    int n = 1;
    while (n < (int)max(a.size(), b.size())) n <<= 1;   // BUG: big enough for a and b, not for the product
    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<ll> r(n);
    for (int i = 0; i < n; i++) r[i] = llround(fa[i].real());
    return r;
}

int main() {
    vector<ll> a = {1, 2, 3}, b = {4, 5, 6};          // (1 + 2x + 3x^2)(4 + 5x + 6x^2)
    cout << "size 4:";
    for (ll v : multiplyTooSmall(a, b)) cout << " " << v;
    cout << "\ncorrect:";
    for (ll v : multiply(a, b)) cout << " " << v;
    cout << "\n";
}
size 4: 22 13 28 27
correct: 4 13 28 27 18

The coefficient 18 of x⁴ wrapped round to x⁰: 4 + 18 = 22.

Mini project

Big-number calculator. Read two numbers with up to 10^5 digits each and print their sum, their difference (with a sign) and their product (FFT + carries). Check the product with casting out nines: the digit sum of the product mod 9 must equal (digit sum of x) · (digit sum of y) mod 9. Then add Lunch Combos with a budget: after the convolution, prefix sums answer "how many combos cost at most B?" for many budgets B in O(1) each.

Practice

These are the homework problems from the episode, plus one warm-up. Each solution below was compiled and run; the solutions to 2 and 3 were also checked against a brute force on 200 random tests each (0 mismatches). To keep the page short, each one starts with the #include, fft and multiply from Problem F1, exactly as above.

1. Pairs by their difference. Count, for every d, the pairs (main, drink) with a[i] − b[j] = d.

Solution

Reverse one array: put drink price v at index mb − v (mb = the most expensive drink). Then index k of the product means a − b = k − mb.

// #include, fft and multiply: exactly as in Problem F1 above

int main() {                                        // count pairs with a[i] - b[j] = d
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (auto& v : a) cin >> v;
    for (auto& v : b) cin >> v;
    int mb = *max_element(b.begin(), b.end());
    vector<ll> ca(*max_element(a.begin(), a.end()) + 1), rb(mb + 1);
    for (int v : a) ca[v]++;
    for (int v : b) rb[mb - v]++;                   // reversed: price v sits at index mb - v
    vector<ll> c = multiply(ca, rb);                // index k means a - b = k - mb
    for (int k = 0; k < (int)c.size(); k++)
        if (c[k]) cout << k - mb << ": " << c[k] << "\n";
}

On the Lunch Combos sample (4 3 / 1 2 3 5 / 2 4 4):

-3: 2
-2: 2
-1: 3
0: 1
1: 3
3: 1

For example d = −1: 1 − 2 once and 3 − 4 twice.

2. Triples with a given sum. Pick 3 different items from one list of prices: for every total s, how many ways?

Solution

A(x)³ counts ordered picks where repeats are allowed. Remove the picks that use one item twice (A(x²) · A(x), three positions for the odd one out) and add back the ones that use it three times (A(x³)): ways = (A³ − 3·A(x²)·A(x) + 2·A(x³)) / 6. Precision: A(x)³ has coefficients up to n³, so this needs n³ well below 10^15 (for example n ≤ 2·10^4); for more, use the NTT with a modulus.

// #include, fft and multiply: exactly as in Problem F1 above

int main() {                                        // pick 3 different items: combos for every total
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& v : a) cin >> v;
    int mx = *max_element(a.begin(), a.end());
    vector<ll> A(mx + 1), A2(2 * mx + 1), A3(3 * mx + 1);
    for (int v : a) A[v]++, A2[2 * v]++, A3[3 * v]++; // A(x), A(x^2), A(x^3)
    vector<ll> cube = multiply(multiply(A, A), A);   // ordered triples, repeats allowed
    vector<ll> twoSame = multiply(A2, A);            // triples where two picks are the same item
    for (int s = 0; s < (int)cube.size(); s++) {
        ll ways = cube[s] - 3 * (s < (int)twoSame.size() ? twoSame[s] : 0) + 2 * A3[s];
        if (ways) cout << s << ": " << ways / 6 << "\n";
    }
}
6
1 2 2 3 4 5
5: 1
6: 2
7: 3
8: 4
9: 4
10: 3
11: 2
12: 1

For example s = 5 has one way: {1, 2, 2}, using the two different items priced 2. s = 7 has three: {1, 2, 4} twice (either 2) and {2, 2, 3}. (Checked against itertools.combinations in Python.)

3. Wildcard matching. A text and a pattern of lowercase letters, where ? matches any letter. Print every position where the pattern matches.

Solution

Give each letter a value 1 to 26 and ? the value 0. Position i matches when Σ_j p_j · t_(i+j) · (p_j − t_(i+j))² = 0: every term is ≥ 0, and it is 0 exactly when the letters are equal or one is a wildcard. Expanded, it is Σ p³t − 2 Σ p²t² + Σ pt³: three convolutions with the pattern reversed.

// #include, fft and multiply: exactly as in Problem F1 above

int main() {                                        // wildcard matching: '?' matches any letter
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string t, p;
    cin >> t >> p;
    int n = t.size(), m = p.size();
    if (m > n) { cout << "\n"; return 0; }
    auto val = [](char ch) { return ch == '?' ? 0LL : (ll)(ch - 'a' + 1); };
    vector<ll> t1(n), t2(n), t3(n), p1(m), p2(m), p3(m);
    for (int i = 0; i < n; i++) { ll v = val(t[i]); t1[i] = v; t2[i] = v * v; t3[i] = v * v * v; }
    for (int j = 0; j < m; j++) { ll v = val(p[m - 1 - j]); p1[j] = v; p2[j] = v * v; p3[j] = v * v * v; }   // reversed
    vector<ll> x = multiply(p3, t1), y = multiply(p2, t2), z = multiply(p1, t3);
    // position i matches when sum over j of p*t*(p - t)^2 = p^3 t - 2 p^2 t^2 + p t^3 is 0
    for (int i = 0; i + m <= n; i++) {
        int k = i + m - 1;
        if (x[k] - 2 * y[k] + z[k] == 0) cout << i << " ";
    }
    cout << "\n";
}
abacabad a?a
0 2 4

aba at 0, aca at 2, aba at 4.

4. Square a 10^6-digit number. Multiply a number by itself.

Solution

The same multiply with b = a: need = 2·10^6 − 1, N = 2^21. Columns are at most 81 · 10^6 ≈ 8·10^7: still safe in doubles. A random 10^6-digit number (mt19937 gen(82), first digit 9):

// #include, fft and multiply: exactly as in Problem F1 above

int main() {                                        // square a 10^6-digit number
    mt19937 gen(82);
    string x(1000000, '0');
    for (auto& d : x) d = '0' + gen() % 10;
    x[0] = '9';
    vector<ll> a(x.size());
    for (int i = 0; i < (int)x.size(); i++) a[i] = x[x.size() - 1 - i] - '0';
    vector<ll> c = multiply(a, a);                  // squaring: one number times itself
    c.push_back(0);
    for (int i = 0; i + 1 < (int)c.size(); i++) {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    if (getenv("DUMP")) {                           // print the whole input and square, for checking
        cout << x << "\n";
        for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
        cout << "\n";
        return 0;
    }
    cout << c.size() << " digits, starting ";
    for (int i = c.size() - 1; i >= (int)c.size() - 15; i--) cout << c[i];
    cout << ", ending ";
    for (int i = 14; i >= 0; i--) cout << c[i];
    cout << "\n";
}
2000000 digits, starting 889466383581260, ending 930533177532225

About 0.3 seconds. With DUMP=1 it prints the number and its square; Python's big integers gave the same 2000000 digits.

5. Pairs from one shop. For every total s, how many pairs i < j from one list have a[i] + a[j] = s?

Solution

A(x)² counts ordered pairs where an item may pair with itself: remove (i, i) at 2·a[i], then halve, because (i, j) and (j, i) are both counted.

// #include, fft and multiply: exactly as in Problem F1 above

int main() {                                        // pairs i < j from ONE shop with a[i] + a[j] = s
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& v : a) cin >> v;
    vector<ll> A(*max_element(a.begin(), a.end()) + 1);
    for (int v : a) A[v]++;
    vector<ll> c = multiply(A, A);                  // ordered pairs, an item may pair with itself
    for (int v : a) c[2 * v]--;                     // remove (i, i)
    for (int s = 2; s < (int)c.size(); s++) cout << c[s] / 2 << " ";   // (i, j) and (j, i) counted twice
    cout << "\n";
}
5
1 2 2 3 5
0 2 2 2 1 2 1 0 0

Totals 2 to 10. Total 4 has two pairs: 1 + 3 and 2 + 2 (the two items priced 2).

Quick quiz

// a has 300 coefficients, b has 213
// smallest power-of-two size n for multiply(a, b)?

A) 256 · B) 512 · C) 1024 · D) 513

Answer

B. need = 300 + 213 − 1 = 512, which is already a power of two. 256 would wrap round; 1024 works but is twice as big as needed; 513 is not a power of two.

Interview questions

  1. What is a convolution? c[k] = Σ a[i] · b[k − i]: the coefficients of the product of two polynomials, the column sums of long multiplication.
  2. What does the FFT compute? The values of a polynomial at the N-th roots of unity (the DFT) in O(N log N); the inverse FFT goes back.
  3. Why roots of unity? Their squares are the N/2-th roots of unity, so A(x) = E(x²) + x·O(x²) splits the problem into two halves at every level.
  4. What is a butterfly? The pair u + w·v, u − w·v: one multiplication gives the values at two opposite roots.
  5. Why must the size be a power of two, at least a.size() + b.size() − 1? Power of two for the halving; at least the product's size because the FFT is cyclic and would wrap high coefficients round.
  6. Why llround and not a cast? Doubles come back slightly off; a cast truncates 0.99999999999999989 to 0.
  7. How do you multiply huge numbers? Digits lowest first as coefficients, FFT multiply, then carries, then strip leading zeros (keep one digit).
  8. When is the double FFT not enough? When the results exceed about 10^14 to 10^15, or when the answer is needed modulo a prime: split the coefficients or use the NTT.

Glossary

Term Meaning Example
Polynomial A sum of terms a_i · x^i 3 + 2x + x²
Coefficient The number in front of x^i the count of mains at price i
Degree The highest power with a non-zero coefficient 3 + 2x + x² has degree 2
Convolution c[k] = Σ a[i] · b[k − i] combos for every total
Coefficient representation A polynomial as its list of coefficients (3, 2, 1)
Value representation A polynomial as its values at N points N values decide degree < N
Evaluation Coefficients → values the forward FFT
Interpolation Values → coefficients the inverse FFT
Complex number a + bi with i² = −1, a point in the plane complex<double>
Root of unity A complex w with w^N = 1 the 8 marks on a clock
DFT The values A(w^k) for k = 0 … N − 1 what the FFT computes
FFT The fast O(N log N) algorithm for the DFT Cooley-Tukey, 1965
Even/odd split A(x) = E(x²) + x · O(x²) two half-size problems
Butterfly u + w·v and u − w·v from one product a[i + k] = u + v
Bit-reversal Reordering by indices with reversed bits 0 4 2 6 1 5 3 7
Inverse transform The same FFT with w⁻¹, then divide by N fft(fa, true)
Cyclic convolution Coefficient k lands at k mod N the wrap-around bug
Power of two 1, 2, 4, 8, … : sizes the FFT can halve 512 in the quiz
llround Round a double to the nearest long long 0.99999999999999989 → 1
Carry Moving c[i] / 10 into the next column 15 → 5, carry 1
Leading zero A zero digit in front of a number 000000 instead of 0
Precision How many bits a double keeps exactly (53) about 9·10^15
NTT The FFT modulo a prime, exact next episode
Stress test Fast vs brute force on random inputs all 500 tests passed

Summary

  • Counting pairs by their sum is a convolution, and a convolution is polynomial multiplication.
  • With values instead of coefficients, a product is N multiplications. At the roots of unity, A(x) = E(x²) + x·O(x²) halves the work: the FFT, O(N log N). The inverse is the same with w⁻¹, then divide by N.
  • Size: a power of two ≥ a.size() + b.size() − 1 (otherwise it wraps round). Convert back with llround, never a cast.
  • Big numbers: digits lowest first, FFT multiply, carries, strip leading zeros but keep one digit. Doubles are safe while the results stay well below 10^15; beyond that, the NTT.

Solutions in C++, Java and Python

The Java versions use a hand-written iterative FFT on double arrays (the same algorithm as the C++). The Python versions use numpy's FFT (numpy.fft.rfft / irfft, numpy 2.5.3 here), because a pure-Python FFT is far too slow for N = 2^20. All three were run on the samples, and on the full random big inputs (the C++ generators' numbers written to a file): the outputs were identical, byte for byte after whitespace (Java about 0.8 s and Python about 0.4 s on each big input).

Problem F1 · Lunch Combos

C++

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

using cd = complex<double>;

void fft(vector<cd>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // reorder: bit-reversed indices
        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) {        // merge halves: len/2 -> len
        double ang = 2 * M_PI / len * (inv ? -1 : 1);
        vector<cd> w(len / 2);
        for (int k = 0; k < len / 2; k++) w[k] = polar(1.0, ang * k);   // roots of unity
        for (int i = 0; i < n; i += len)
            for (int k = 0; k < len / 2; k++) {
                cd u = a[i + k], v = a[i + k + len / 2] * w[k];
                a[i + k] = u + v;                   // E + w O
                a[i + k + len / 2] = u - v;         // E - w O
            }
    }
    if (inv) for (auto& x : a) x /= n;
}

vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;                      // a power of two, big enough
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n);
    fb.resize(n);
    fft(fa, false);
    fft(fb, false);                                 // coefficients -> values
    for (int i = 0; i < n; i++) fa[i] *= fb[i];      // multiply the values
    fft(fa, true);                                  // values -> coefficients
    vector<ll> r(need);
    for (int i = 0; i < need; i++) r[i] = llround(fa[i].real());
    return r;
}

vector<ll> counts(const vector<int>& a) {           // cnt[v] = items that cost v
    vector<ll> cnt(*max_element(a.begin(), a.end()) + 1);
    for (int v : a) cnt[v]++;
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (auto& v : a) cin >> v;
    for (auto& v : b) cin >> v;
    vector<ll> c = multiply(counts(a), counts(b));
    for (int s = 2; s < (int)c.size(); s++) cout << c[s] << " ";
}

Java

import java.util.*;
import java.io.*;

public class Main {
    // in-place iterative FFT on separate real and imaginary arrays
    static void fft(double[] re, double[] im, boolean inv) {
        int n = re.length;
        for (int i = 1, j = 0; i < n; i++) {                // reorder: bit-reversed indices
            int bit = n >> 1;
            for (; (j & bit) != 0; bit >>= 1) j ^= bit;
            j ^= bit;
            if (i < j) {
                double t = re[i]; re[i] = re[j]; re[j] = t;
                t = im[i]; im[i] = im[j]; im[j] = t;
            }
        }
        for (int len = 2; len <= n; len <<= 1) {            // merge halves: len/2 -> len
            double ang = 2 * Math.PI / len * (inv ? -1 : 1);
            int half = len / 2;
            double[] wr = new double[half], wi = new double[half];
            for (int k = 0; k < half; k++) { wr[k] = Math.cos(ang * k); wi[k] = Math.sin(ang * k); }   // roots of unity
            for (int i = 0; i < n; i += len)
                for (int k = 0; k < half; k++) {
                    int p = i + k, q = i + k + half;
                    double vr = re[q] * wr[k] - im[q] * wi[k];
                    double vi = re[q] * wi[k] + im[q] * wr[k];
                    re[q] = re[p] - vr; im[q] = im[p] - vi;   // E - w O
                    re[p] += vr;        im[p] += vi;          // E + w O
                }
        }
        if (inv) for (int i = 0; i < n; i++) { re[i] /= n; im[i] /= n; }
    }
    static long[] multiply(long[] a, long[] b) {
        int need = a.length + b.length - 1, n = 1;
        while (n < need) n <<= 1;                           // a power of two, big enough
        double[] ar = new double[n], ai = new double[n], br = new double[n], bi = new double[n];
        for (int i = 0; i < a.length; i++) ar[i] = a[i];
        for (int i = 0; i < b.length; i++) br[i] = b[i];
        fft(ar, ai, false);
        fft(br, bi, false);                                 // coefficients -> values
        for (int i = 0; i < n; i++) {                       // multiply the values
            double r = ar[i] * br[i] - ai[i] * bi[i];
            ai[i] = ar[i] * bi[i] + ai[i] * br[i];
            ar[i] = r;
        }
        fft(ar, ai, true);                                  // values -> coefficients
        long[] r = new long[need];
        for (int i = 0; i < need; i++) r[i] = Math.round(ar[i]);   // round, never truncate
        return r;
    }
    static long[] counts(int[] a) {                         // cnt[v] = items that cost v
        int mx = 0;
        for (int v : a) mx = Math.max(mx, v);
        long[] cnt = new long[mx + 1];
        for (int v : a) cnt[v]++;
        return cnt;
    }
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = nextInt(in), m = nextInt(in);
        int[] a = new int[n], b = new int[m];
        for (int i = 0; i < n; i++) a[i] = nextInt(in);
        for (int i = 0; i < m; i++) b[i] = nextInt(in);
        long[] c = multiply(counts(a), counts(b));
        StringBuilder out = new StringBuilder();
        for (int s = 2; s < c.length; s++) out.append(c[s]).append(' ');
        System.out.println(out);
    }
    static int nextInt(DataInputStream in) throws IOException {
        int r = 0, ch = in.read();
        while (ch < '0') ch = in.read();
        while (ch >= '0') { r = r * 10 + ch - '0'; ch = in.read(); }
        return r;
    }
}
0 1 1 3 2 3 0 2

Python

import sys
import numpy as np

def multiply(a, b):                      # integer convolution with numpy's FFT
    need = len(a) + len(b) - 1
    n = 1
    while n < need:                      # a power of two, big enough
        n <<= 1
    fa = np.fft.rfft(a, n)               # coefficients -> values
    fb = np.fft.rfft(b, n)
    c = np.fft.irfft(fa * fb, n)[:need]  # multiply the values, then values -> coefficients
    return np.rint(c).astype(np.int64)   # round, never truncate

data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = np.array(data[2:2 + n], dtype=np.int64)
b = np.array(data[2 + n:2 + n + m], dtype=np.int64)
c = multiply(np.bincount(a).astype(np.float64), np.bincount(b).astype(np.float64))   # counts by price
print(" ".join(map(str, c[2:].tolist())) + " ")
0 1 1 3 2 3 0 2

Problem F2 · Huge Product

C++

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

using cd = complex<double>;

void fft(vector<cd>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // reorder: bit-reversed indices
        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) {        // merge halves: len/2 -> len
        double ang = 2 * M_PI / len * (inv ? -1 : 1);
        vector<cd> w(len / 2);
        for (int k = 0; k < len / 2; k++) w[k] = polar(1.0, ang * k);   // roots of unity
        for (int i = 0; i < n; i += len)
            for (int k = 0; k < len / 2; k++) {
                cd u = a[i + k], v = a[i + k + len / 2] * w[k];
                a[i + k] = u + v;                   // E + w O
                a[i + k + len / 2] = u - v;         // E - w O
            }
    }
    if (inv) for (auto& x : a) x /= n;
}

vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;                      // a power of two, big enough
    vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    fa.resize(n);
    fb.resize(n);
    fft(fa, false);
    fft(fb, false);                                 // coefficients -> values
    for (int i = 0; i < n; i++) fa[i] *= fb[i];      // multiply the values
    fft(fa, true);                                  // values -> coefficients
    vector<ll> r(need);
    for (int i = 0; i < need; i++) r[i] = llround(fa[i].real());
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string x, y;
    cin >> x >> y;
    vector<ll> a(x.size()), b(y.size());
    for (int i = 0; i < (int)x.size(); i++) a[i] = x[x.size() - 1 - i] - '0';   // lowest digit first
    for (int i = 0; i < (int)y.size(); i++) b[i] = y[y.size() - 1 - i] - '0';
    vector<ll> c = multiply(a, b);
    c.push_back(0);
    for (int i = 0; i + 1 < (int)c.size(); i++) {   // carries, like on paper
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();   // no leading zeros
    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
    cout << "\n";
}

Java

import java.util.*;
import java.io.*;

public class Main {
    // in-place iterative FFT on separate real and imaginary arrays
    static void fft(double[] re, double[] im, boolean inv) {
        int n = re.length;
        for (int i = 1, j = 0; i < n; i++) {                // reorder: bit-reversed indices
            int bit = n >> 1;
            for (; (j & bit) != 0; bit >>= 1) j ^= bit;
            j ^= bit;
            if (i < j) {
                double t = re[i]; re[i] = re[j]; re[j] = t;
                t = im[i]; im[i] = im[j]; im[j] = t;
            }
        }
        for (int len = 2; len <= n; len <<= 1) {            // merge halves: len/2 -> len
            double ang = 2 * Math.PI / len * (inv ? -1 : 1);
            int half = len / 2;
            double[] wr = new double[half], wi = new double[half];
            for (int k = 0; k < half; k++) { wr[k] = Math.cos(ang * k); wi[k] = Math.sin(ang * k); }   // roots of unity
            for (int i = 0; i < n; i += len)
                for (int k = 0; k < half; k++) {
                    int p = i + k, q = i + k + half;
                    double vr = re[q] * wr[k] - im[q] * wi[k];
                    double vi = re[q] * wi[k] + im[q] * wr[k];
                    re[q] = re[p] - vr; im[q] = im[p] - vi;   // E - w O
                    re[p] += vr;        im[p] += vi;          // E + w O
                }
        }
        if (inv) for (int i = 0; i < n; i++) { re[i] /= n; im[i] /= n; }
    }
    static long[] multiply(long[] a, long[] b) {
        int need = a.length + b.length - 1, n = 1;
        while (n < need) n <<= 1;                           // a power of two, big enough
        double[] ar = new double[n], ai = new double[n], br = new double[n], bi = new double[n];
        for (int i = 0; i < a.length; i++) ar[i] = a[i];
        for (int i = 0; i < b.length; i++) br[i] = b[i];
        fft(ar, ai, false);
        fft(br, bi, false);                                 // coefficients -> values
        for (int i = 0; i < n; i++) {                       // multiply the values
            double r = ar[i] * br[i] - ai[i] * bi[i];
            ai[i] = ar[i] * bi[i] + ai[i] * br[i];
            ar[i] = r;
        }
        fft(ar, ai, true);                                  // values -> coefficients
        long[] r = new long[need];
        for (int i = 0; i < need; i++) r[i] = Math.round(ar[i]);   // round, never truncate
        return r;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
        StringTokenizer st = new StringTokenizer(br.readLine());
        String x = st.nextToken(), y = st.nextToken();
        long[] a = new long[x.length()], b = new long[y.length()];
        for (int i = 0; i < x.length(); i++) a[i] = x.charAt(x.length() - 1 - i) - '0';   // lowest digit first
        for (int i = 0; i < y.length(); i++) b[i] = y.charAt(y.length() - 1 - i) - '0';
        long[] c = Arrays.copyOf(multiply(a, b), a.length + b.length);   // one extra column for the last carry
        for (int i = 0; i + 1 < c.length; i++) {          // carries, like on paper
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        int top = c.length - 1;
        while (top > 0 && c[top] == 0) top--;             // no leading zeros, keep one digit
        StringBuilder out = new StringBuilder(top + 2);
        for (int i = top; i >= 0; i--) out.append((char) ('0' + c[i]));
        System.out.println(out);
    }
}
1219326311370217952237463801111263526900

Python

import sys
import numpy as np

def multiply(a, b):                      # integer convolution with numpy's FFT
    need = len(a) + len(b) - 1
    n = 1
    while n < need:                      # a power of two, big enough
        n <<= 1
    c = np.fft.irfft(np.fft.rfft(a, n) * np.fft.rfft(b, n), n)[:need]
    return np.rint(c).astype(np.int64)   # round, never truncate

x, y = sys.stdin.read().split()
a = np.frombuffer(x[::-1].encode(), dtype=np.uint8).astype(np.float64) - 48   # lowest digit first
b = np.frombuffer(y[::-1].encode(), dtype=np.uint8).astype(np.float64) - 48
c = multiply(a, b).tolist() + [0]        # one extra column for the last carry
for i in range(len(c) - 1):              # carries, like on paper
    c[i + 1] += c[i] // 10
    c[i] %= 10
while len(c) > 1 and c[-1] == 0:         # no leading zeros, keep one digit
    c.pop()
print("".join(map(str, reversed(c))))
1219326311370217952237463801111263526900