SyntaxPilot
Courses/Competitive Programming/Lesson 83
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 83 of 90

NTT and counting with polynomials

queued

These are the notes for Competitive Programming episode 83. Last episode's FFT multiplied polynomials in O(n log n) with complex numbers and doubles. Today the answers are wanted modulo a prime, and the doubles break: Sweet Boxes shows the double FFT printing 998244325 where the true answer is 998244346 (off by 21). The fix is the number theoretic transform (NTT): the same butterfly, but with roots of unity made of integers modulo 998244353, so every step is exact. A real bug: forgetting + MOD in u − v prints negative numbers (-7, -751330775). Then Club Delegates turns counting into multiplying: each club is the tiny polynomial 1 + s·x, and the product of 200000 of them, taken like a knockout bracket (divide and conquer), runs in O(n log² n) while adding clubs one at a time is O(n²) and TLE. 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

Take a clock with 7 hours, numbered 0 to 6. Start at 1 and keep multiplying by 3, wrapping round the clock (that is, taking the remainder mod 7): 3, then 9 = 2, then 6, then 18 = 4, then 12 = 5, then 15 = 1. The powers of 3 mod 7 are 3, 2, 6, 4, 5, 1: they visit every hour except 0 and come back to 1 after exactly 6 jumps. A number like 3 is called a primitive root.

  • Jump by 3² = 2 instead: 2, 4, 1. Back to 1 after exactly 3 jumps: 2 is a 3rd root of unity, made of integers. In general g^((p − 1)/len) comes back to 1 after exactly len jumps.
  • Halfway round, 3³ = 27 = 6, and 6 · 6 = 36 = 1 on the clock. So 6 behaves exactly like −1 (6 = 7 − 1). That is the property the FFT butterfly needs (w^(len/2) = −1), so u + w·v and u − w·v still work.

The FFT never needed complex numbers as such; it needed numbers whose powers go round in a circle and come back to 1. A clock modulo a prime has them.

Problem N1 · Sweet Boxes

(Written for this course.)

  • a[i] = the number of ways to fill box A with i sweets, for i < n, given modulo 998244353.
  • b[j] = the number of ways to fill box B with j sweets, for j < m, also modulo 998244353.
  • For every total t, print the number of ways to fill both boxes with t sweets in all: c[t] = Σ a[i] · b[t − i], modulo 998244353.
  • n, m ≤ 5·10^5; every a[i], b[j] is already in [0, 998244353).

The input is n m, then the n values of a, then the m values of b.

3 2
998244352 5 123456789
998244352 2

It is last episode's convolution again, but now every number can be close to 10^9.

Checking the sample by hand. 998244352 = p − 1, which is −1 modulo p. So a = (−1, 5, 123456789) and b = (−1, 2):

  • c[0] = (−1)(−1) = 1
  • c[1] = (−1)·2 + 5·(−1) = −7, which is p − 7 = 998244346
  • c[2] = 5·2 + 123456789·(−1) = −123456779, which is 874787574
  • c[3] = 123456789 · 2 = 246913578

A small sanity input (1 + 2x + 3x² times 4 + 5x):

3 2
1 2 3
4 5

Attempt 1: last episode's FFT, then % MOD (Wrong Answer)

The only change from episode 82: round each coefficient, then take the remainder modulo the prime.

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

const ll MOD = 998244353;

using cd = complex<double>;
void fft(vector<cd>& a, bool inv) {                // episode 82
    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) {
        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);
        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;
                a[i + k + len / 2] = u - v;
            }
    }
    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;
    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(need);
    for (int i = 0; i < need; i++) r[i] = llround(fa[i].real()) % MOD;   // round, then mod
    return r;
}

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

On the small input:

4 13 22 15

Correct. On the sample:

1 998244325 874787564 246913557

The slow, exact way

The double loop, taking % MOD after every product (each product is below 10^18, so it fits in long long):

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

const ll MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<ll> a(n), b(m);
    for (auto& v : a) cin >> v;
    for (auto& v : b) cin >> v;
    vector<ll> c(n + m - 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) c[i + j] = (c[i + j] + a[i] * b[j]) % MOD;   // the slow, exact way
    for (ll v : c) cout << v << " ";
}

Small input:

4 13 22 15

Sample:

1 998244346 874787574 246913578

So the FFT was off by 21 in the second place, and the last coefficient (246913557 instead of 246913578) is wrong too: Wrong Answer. The slow loop is exact, but O(n·m) = 2.5·10^11 for the full limits.

Why the doubles broke

  • One product a[i] · b[j] can be up to 10^9 · 10^9 = 10^18.
  • A column of the convolution adds up to 5·10^5 of them: about 5·10^23.
  • A double keeps a 53-bit mantissa, about 16 decimal digits (2^53 ≈ 9·10^15). Everything after that is rounding noise, and the FFT's error grows with the largest values in the whole transform, so even the small coefficients come out a few dozen units off.
  • % MOD depends on exactly those last digits. Off by 21 before the remainder means off by 21 after it.

llround rounds the error away only while the true values are small enough that the error stays below 0.5 (as with 1 2 3 times 4 5). Here a single product is already above 2^53, so it can't. We need roots of unity made of integers, modulo p: then nothing is ever rounded.

Roots of unity modulo a prime

From the clock: modulo a prime p, take a primitive root g (its powers g, g², …, g^(p−1) visit every nonzero remainder). Then w = g^((p − 1)/len) satisfies w^len = g^(p−1) = 1 (Fermat's little theorem), and no smaller power of w is 1. So w is a len-th root of unity, and w^(len/2) is −1, exactly as e^(2πi/len) was in the FFT.

This only works when len divides p − 1, and the FFT uses lengths that are powers of two. So we need a prime where p − 1 has many factors of 2.

Why every contest uses 998244353

  • 998244353 − 1 = 119 · 2^23. Every power of two up to 2^23 = 8388608 ≈ 8.4·10^6 divides p − 1, so there is a root for every transform length up to 8.4 million. N1's largest length is 2^20 = 1048576.
  • 3 is a primitive root mod 998244353, like 3 on the 7-hour clock.
  • The root for length len: w = 3^((p − 1)/len) mod p.
  • The inverse transform needs w⁻¹ and a division by n. Dividing is multiplying by an inverse, and Fermat's little theorem (episode 22) gives it: x⁻¹ = x^(p − 2) mod p. So w⁻¹ = w^(p − 2) and n⁻¹ = n^(p − 2).
  • It is also below 2^30, so the sum of two values fits in int and a product of two fits in long long (below 10^18 < 9.2·10^18).

The rest is last episode's FFT, line for line, with integers. That is the number theoretic transform.

The NTT butterfly

For each length len = 2, 4, 8, …, n, each block of len values is combined from its two halves. With w running over the powers of the root, for k = 0 … len/2 − 1:

  • u = a[i + k], v = a[i + k + len/2] · w
  • a[i + k] = u + v, a[i + k + len/2] = u − v (all mod p)

That is the butterfly: two values in, two values out. Before the loops, the values are put in bit-reversed order (index 6 = 110 in binary swaps with index 3 = 011), exactly as in the FFT, so the blocks can be combined in place. Then multiply is: pad both to a power of two ≥ n + m − 1, transform both, multiply pointwise, transform back.

Attempt 2: the NTT, with the negative % bug

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<ll> a(n), b(m);
    for (auto& v : a) cin >> v;
    for (auto& v : b) cin >> v;
    vector<ll> c = multiply(a, b);
    for (ll v : c) cout << v << " ";
}
1 -7 874787574 -751330775

Minus 7, and a negative number at the end: Wrong Answer. In C++, the remainder of a negative number is negative: (u − v) % MOD with u < v gives a value between −(p − 1) and −1. So −7 % p is −7, not p − 7, and −751330775 is 246913578 − 998244353. (Python's % is never negative, which is why the bug does not show up there.)

The fix: (u − v + MOD) % MOD

Add MOD before taking the remainder, so the value is never negative (u and v are both in [0, p), so u − v + p is in [1, 2p)).

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<ll> a(n), b(m);
    for (auto& v : a) cin >> v;
    for (auto& v : b) cin >> v;
    vector<ll> c = multiply(a, b);
    for (ll v : c) cout << v << " ";
}
1 998244346 874787574 246913578

Exactly the slow double loop.

Half a million values in each box. The same NTT, with n = m = 500000 random values from mt19937 gen(83), printed as one hash so the screen stays readable:

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

int main() {
    mt19937 gen(83);
    int n = 500000, m = 500000;
    vector<ll> a(n), b(m);
    for (auto& v : a) v = gen() % MOD;
    for (auto& v : b) v = gen() % MOD;
    vector<ll> c = multiply(a, b);
    ll check = 0;
    for (int i = 0; i < (int)c.size(); i++) check = (check * 31 + c[i]) % MOD;   // one number for all of c
    cout << c.size() << " coefficients, hash " << check << "\n";
}
999999 coefficients, hash 202070466

Nearly a million coefficients, in a fraction of a second (0.36 s here).

Stress test

300 random pairs of polynomials, lengths 1 to 80, values right up to the prime, against the slow loop:

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

int main() {
    mt19937 gen(83);
    for (int it = 1; it <= 300; it++) {
        vector<ll> a(gen() % 80 + 1), b(gen() % 80 + 1);
        for (auto& v : a) v = gen() % MOD;
        for (auto& v : b) v = gen() % MOD;
        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] = (slow[i + j] + a[i] * b[j]) % MOD;
        if (slow != multiply(a, b)) { cout << "mismatch on test " << it; return 0; }
    }
    cout << "all 300 tests passed";
}
all 300 tests passed

The NTT is exact where the FFT was not.

Problem N2 · Club Delegates

(Written for this course.)

  • A college has n clubs; club i has s[i] members. n ≤ 2·10^5, s[i] ≤ 10^9.
  • The festival committee needs exactly k delegates, and at most one from each club.
  • Count the ways, modulo 998244353.

The input is n k, then the n club sizes.

3 2
2 3 1

Clubs of 2, 3 and 1 members, choose 2: 2·3 + 2·1 + 3·1 = 11.

Counting with polynomials

Think of each club as a tiny polynomial, its generating polynomial:

1 + s[i]·x: the 1 means we skip the club, and s[i]·x means we pick one of its s[i] members, which uses one seat (one power of x).

Multiply all the clubs' polynomials. Choosing one term from each bracket is choosing what to do with each club; the exponents add up to the number of seats used and the coefficients multiply to the number of ways. So:

answer = the coefficient of x^k in (1 + s[0]x)(1 + s[1]x) … (1 + s[n−1]x).

Reading off one coefficient is called coefficient extraction. For the sample, (1 + 2x)(1 + 3x)(1 + x) = 1 + 6x + 11x² + 6x³. Counting became multiplying.

Attempt 1: add clubs one at a time (TLE)

dp[j] = the number of ways to pick j delegates from the clubs so far. Each new club is skipped, or gives one of its members: dp[j] += dp[j − 1] · s[i], with j going down so each club is used once. This is multiplying by (1 + s[i]x) one club at a time.

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

const ll MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> s(n);
    for (auto& v : s) cin >> v;
    vector<ll> dp(n + 1, 0);                          // dp[j] = ways to pick j people so far
    dp[0] = 1;
    for (int i = 0; i < n; i++)                       // add club i: skip it, or pick one of s[i]
        for (int j = i + 1; j >= 1; j--) dp[j] = (dp[j] + dp[j - 1] * (s[i] % MOD)) % MOD;
    cout << (k <= n ? dp[k] : 0) << "\n";
}
11

The table goes [1] → [1, 2] → [1, 5, 6] → [1, 6, 11, 6]. Correct. Now 200000 clubs (mt19937 gen(83), sizes up to 10^9, k = 100000):

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

const ll MOD = 998244353;

int main() {
    mt19937 gen(83);
    int n = 200000, k = 100000;                     // 200000 clubs
    vector<ll> s(n);
    for (auto& v : s) v = gen() % 1000000000 + 1;
    vector<ll> dp(n + 1, 0);                          // dp[j] = ways to pick j people so far
    dp[0] = 1;
    for (int i = 0; i < n; i++)                       // add club i: skip it, or pick one of s[i]
        for (int j = i + 1; j >= 1; j--) dp[j] = (dp[j] + dp[j - 1] * (s[i] % MOD)) % MOD;
    cout << (k <= n ? dp[k] : 0) << "\n";
}

Club i updates i + 1 entries, so this is about n²/2 = 2·10^10 updates. It runs far beyond any time limit (still running when stopped after 10 seconds here): Time Limit Exceeded in the SyntaxPilot compiler.

A knockout bracket: divide and conquer

Adding one club at a time is like a long queue: one huge polynomial times one tiny one, again and again. Instead, run it like a knockout tournament. With clubs of 2, 3, 1 and 4 members:

Round 0:   1 + 2x      1 + 3x      1 + x       1 + 4x
Round 1:     1 + 5x + 6x²            1 + 5x + 4x²
Final:          1 + 10x + 35x² + 50x³ + 24x⁴

The final polynomial holds the answer for every k at once: 35 ways to choose 2 delegates from these four clubs.

In code, the product of a range of clubs is the product of its left half times the product of its right half:

prod(l, r) = prod(l, mid) · prod(mid, r)

Why it is O(n log² n). Look at one round of the bracket: the polynomials in that round have total degree n. Multiplying them with the NTT costs O(n log n) for the round. There are about log₂ n rounds (about 18 for 200000 clubs), so the total is O(n log² n).

Why one at a time is O(n²), even with the NTT. The sizes are what matter. The plain loop does 1 + 2 + … + n ≈ n²/2 updates. Using the NTT for "huge times tiny" is even worse: n multiplications, each of size up to n, is O(n² log n). Pairing equal sizes is what makes it fast.

The bracket in code

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

vector<ll> prod(const vector<ll>& s, int l, int r) {   // (1 + s[l] x) ... (1 + s[r-1] x)
    if (r - l == 1) return {1, s[l] % MOD};
    int mid = (l + r) / 2;
    return multiply(prod(s, l, mid), prod(s, mid, r));   // two halves of equal size
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> s(n);
    for (auto& v : s) cin >> v;
    vector<ll> c = prod(s, 0, n);
    cout << (k <= n ? c[k] : 0) << "\n";
}

Sample:

11

Edge case: 5 delegates from only 3 clubs:

3 5
2 3 1
0

0 ways: there aren't enough clubs (the product has degree 3, so the k <= n check prints 0).

Comparing the bracket and the loop

20000 clubs, k = 10000: small enough that the plain loop finishes (2·10^8 updates), so the two can be compared. The bracket first:

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

vector<ll> prod(const vector<ll>& s, int l, int r) {   // (1 + s[l] x) ... (1 + s[r-1] x)
    if (r - l == 1) return {1, s[l] % MOD};
    int mid = (l + r) / 2;
    return multiply(prod(s, l, mid), prod(s, mid, r));   // two halves of equal size
}

int main() {
    mt19937 gen(83);
    int n = 20000, k = 10000;                       // 20000 clubs: small enough for the DP
    vector<ll> s(n);
    for (auto& v : s) v = gen() % 1000000000 + 1;
    vector<ll> c = prod(s, 0, n);
    cout << (k <= n ? c[k] : 0) << "\n";
}
361874299

And the plain loop on the same clubs:

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

const ll MOD = 998244353;

int main() {
    mt19937 gen(83);
    int n = 20000, k = 10000;                       // 20000 clubs: small enough for the DP
    vector<ll> s(n);
    for (auto& v : s) v = gen() % 1000000000 + 1;
    vector<ll> dp(n + 1, 0);                          // dp[j] = ways to pick j people so far
    dp[0] = 1;
    for (int i = 0; i < n; i++)                       // add club i: skip it, or pick one of s[i]
        for (int j = i + 1; j >= 1; j--) dp[j] = (dp[j] + dp[j - 1] * (s[i] % MOD)) % MOD;
    cout << (k <= n ? dp[k] : 0) << "\n";
}
361874299

The same. Finally, 200000 clubs with the bracket:

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

vector<ll> prod(const vector<ll>& s, int l, int r) {   // (1 + s[l] x) ... (1 + s[r-1] x)
    if (r - l == 1) return {1, s[l] % MOD};
    int mid = (l + r) / 2;
    return multiply(prod(s, l, mid), prod(s, mid, r));   // two halves of equal size
}

int main() {
    mt19937 gen(83);
    int n = 200000, k = 100000;                     // 200000 clubs
    vector<ll> s(n);
    for (auto& v : s) v = gen() % 1000000000 + 1;
    vector<ll> c = prod(s, 0, n);
    cout << (k <= n ? c[k] : 0) << "\n";
}
119113075

Well inside the time limit (the video shows about half a second; 1.5 s on this machine while a video render was running).

Complexity vs the constraints

Method Time Verdict
N1: double FFT, then % MOD O(N log N) fast, but WA (off by 21)
N1: double loop O(n·m) = 2.5·10^11 TLE
N1: NTT convolution, N = 2^20 O(N log N): three transforms of about 10^7 butterflies each accepted (0.36 s)
N2: clubs one at a time O(n²) ≈ 2·10^10 TLE
N2: one at a time with NTT O(n² log n) even worse
N2: bracket of NTTs O(n log² n), about 18 rounds accepted

Memory: O(N) for N1; O(n) for N2 (the recursion only keeps the polynomials on the current path alive). Every product of two values below p is below 10^18: long long, no overflow, no rounding.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
double FFT for answers mod p 1 998244325 874787564 246913557 (off by 21) sums near 10^23 need far more than 53 bits NTT
a[i + k + len/2] = (u − v) % MOD 1 -7 874787574 -751330775 C++ % keeps the sign (u − v + MOD) % MOD
NTT with a prime like 10^9 + 7 no root for len = 4 or more p − 1 = 2 · 500000003: only one factor of 2 use 998244353 (or three NTT primes + CRT)
clubs one at a time TLE (2·10^10 updates) huge × tiny, n times divide and conquer, equal halves
forgetting the inverse root or n⁻¹ coefficients multiplied by n, or reversed the inverse NTT needs both w^(p−2) and n^(p−2)
padding below n + m − 1 high coefficients wrap onto low ones the transform is cyclic length = power of two ≥ n + m − 1
s[i] not reduced mod p overflow in dp[j − 1] · s[i] s[i] ≤ 10^9 > p s[i] % MOD first
reading c[k] when k > n out-of-range access the product has degree n print 0 when k > n

Mini project

Festival planner. Read the clubs and print the number of ways to choose k delegates for every k from 0 to n (one bracket gives them all). Add a switch for "at most two per club" (practice 1). Stress test both against the plain DP on 200 random small inputs, and against a brute force over subsets on tiny ones. Finally, print how long the bracket and the DP take for n = 1000, 10000, 100000 and check that the bracket's time grows like n log² n.

Practice

These follow the episode's homework. Every program below was compiled and run; the outputs are real.

1. At most two delegates per club. Club i can now give 0, 1 or 2 members: its polynomial is 1 + s·x + C(s, 2)·x², with C(s, 2) = s(s − 1)/2 computed mod p using the inverse of 2. Same bracket.

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

vector<ll> prod2(const vector<ll>& s, int l, int r) {   // (1 + s x + C(s,2) x^2) for each club
    if (r - l == 1) {
        ll a = s[l] % MOD, c2 = a * ((s[l] - 1) % MOD) % MOD * power(2, MOD - 2) % MOD;
        return {1, a, c2};
    }
    int mid = (l + r) / 2;
    return multiply(prod2(s, l, mid), prod2(s, mid, r));
}

int main() {                                        // at most TWO delegates per club
    int n, k;
    cin >> n >> k;
    vector<ll> s(n);
    for (auto& v : s) cin >> v;
    vector<ll> c = prod2(s, 0, n);
    cout << (k < (int)c.size() ? c[k] : 0) << "\n";
}
3 3
2 3 1
19

Check: there are C(6, 3) = 20 ways to choose 3 of the 6 people, and the only forbidden one takes all 3 members of the second club: 20 − 1 = 19. A brute force over all subsets (not shown) also prints 19. With k = 2 every pair is allowed, and the program prints 15 = C(6, 2).

2. Square a polynomial with a single forward transform. Multiplying a by itself does not need two forward NTTs: transform once, square every value, transform back.

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

int main() {                                        // square a polynomial with ONE forward transform
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& v : a) cin >> v;
    int need = 2 * n - 1, len = 1;
    while (len < need) len <<= 1;
    a.resize(len);
    ntt(a, false);                                  // one forward transform
    for (auto& x : a) x = x * x % MOD;              // square every value
    ntt(a, true);
    for (int i = 0; i < need; i++) cout << a[i] << " ";
    cout << "\n";
}
3
1 2 3
1 4 10 12 9

(1 + 2x + 3x²)² = 1 + 4x + 10x² + 12x³ + 9x⁴. Two transforms instead of three: about a third faster.

3. Dice totals mod p. d dice with f faces each: the number of ways to roll every total from d to d·f, modulo 998244353. One die is x + x² + … + x^f; d dice are its d-th power. Use fast exponentiation (episode 21) with polynomials instead of numbers: O(N log N · log d).

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

int main() {                                        // d dice with f faces: ways for every total
    ll d, f;
    cin >> d >> f;
    vector<ll> die(f + 1, 1);
    die[0] = 0;                                     // x + x^2 + ... + x^f
    vector<ll> res = {1};
    for (ll e = d; e; e >>= 1) {                    // fast exponentiation, with polynomials
        if (e & 1) res = multiply(res, die);
        if (e > 1) die = multiply(die, die);
    }
    for (ll t = d; t <= d * f; t++) cout << res[t] << " ";
    cout << "\n";
}

Three six-sided dice (input 3 6), totals 3 to 18:

1 3 6 10 15 21 25 27 27 25 21 15 10 6 3 1

Two dice (input 2 6), totals 2 to 12:

1 2 3 4 5 6 5 4 3 2 1

27 ways each for totals 10 and 11: the middle of the bell. For large d the polynomial res has degree d·f, so this is fast as long as d·f ≤ 8·10^6 (the longest NTT for this prime).

4. Is a prime NTT-friendly? For p = 7, 998244353 and 10^9 + 7, print how many factors of 2 the number p − 1 has (so the longest power-of-two NTT), and whether 3 is a primitive root. Test: g is a primitive root exactly when g^((p − 1)/q) ≠ 1 for every prime factor q of p − 1.

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

ll power(ll b, ll e, ll m) {
    ll r = 1;
    b %= m;
    for (; e; e >>= 1, b = b * b % m)
        if (e & 1) r = r * b % m;
    return r;
}

int main() {                                        // is a prime NTT-friendly? is 3 a primitive root?
    for (ll p : {7LL, 998244353LL, 1000000007LL}) {
        ll q = p - 1, two = 0;
        while (q % 2 == 0) q /= 2, two++;
        vector<ll> primes;                          // prime factors of p - 1
        ll x = p - 1;
        for (ll d = 2; d * d <= x; d++)
            if (x % d == 0) { primes.push_back(d); while (x % d == 0) x /= d; }
        if (x > 1) primes.push_back(x);
        bool prim = true;
        for (ll r : primes) if (power(3, (p - 1) / r, p) == 1) prim = false;
        cout << "p = " << p << ": p - 1 = 2^" << two << " * " << q
             << ", longest NTT = " << (1LL << two) << ", 3 is " << (prim ? "" : "not ") << "a primitive root\n";
    }
}
p = 7: p - 1 = 2^1 * 3, longest NTT = 2, 3 is a primitive root
p = 998244353: p - 1 = 2^23 * 119, longest NTT = 8388608, 3 is a primitive root
p = 1000000007: p - 1 = 2^1 * 500000003, longest NTT = 2, 3 is not a primitive root

10^9 + 7 has only one factor of 2 in p − 1, so a "root of unity" exists only for length 2: useless for the NTT. (3 is not even a primitive root there; 5 is. For 10^9 + 7 answers, run the NTT modulo three friendly primes and combine with the Chinese remainder theorem, episode 26: the homework's hard question.)

5. The 7-hour clock. For every g from 1 to 6, print its powers mod 7 until they return to 1, and the number of jumps (the order of g).

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

int main() {                                        // the 7-hour clock: how many jumps back to 1?
    for (int g = 1; g < 7; g++) {
        cout << g << ":";
        int x = 1, jumps = 0;
        do { x = x * g % 7; jumps++; cout << " " << x; } while (x != 1);
        cout << "   order " << jumps << "\n";
    }
}
1: 1   order 1
2: 2 4 1   order 3
3: 3 2 6 4 5 1   order 6
4: 4 2 1   order 3
5: 5 4 6 2 3 1   order 6
6: 6 1   order 2

3 and 5 are the primitive roots of 7 (order 6). 2 and 4 are 3rd roots of unity, and 6 = −1 is a 2nd root.

6. Think: the number of subsets of each size with sum at most S? (The episode's thinking question.)

Hint

Give every item the two-variable polynomial 1 + x·y^(value): x counts the size, y the sum. You need the coefficients of x^k y^t for t ≤ S. A two-variable product is much heavier; when the values are small, a 2D DP over (size, sum) with O(n² · S) work is often the practical answer, and only the sum alone (one variable) is a plain NTT product.

Quick quiz

// p = 7, primitive root g = 3
// which number is a 6th root of unity that
// first returns to 1 after exactly 6 jumps?

A) 2 · B) 6 · C) 5 · D) 4

Answer

C) 5. Its powers mod 7 are 5, 4, 6, 2, 3, 1: back to 1 for the first time after exactly 6 jumps, so like 3 it is a primitive root. 2 and 4 come back after 3 jumps, and 6 after 2. (Checked with practice 5 above.)

Interview questions

  1. Why does the floating-point FFT fail for convolutions mod 998244353? The true coefficients can reach about 10^23, far beyond the 53-bit mantissa of a double (about 16 digits); the remainder depends on the lost low digits.
  2. What is the NTT? The FFT carried out in the integers modulo a prime, with a modular root of unity g^((p−1)/len) in place of e^(2πi/len). Every step is exact.
  3. Which primes work? Primes p where p − 1 is divisible by a large power of two, such as 998244353 = 119·2^23 + 1 (root 3). The maximum transform length is that power of two.
  4. How do you invert the transform? Run it with the inverse root w^(p−2) and multiply every value by n^(p−2), both by Fermat's little theorem.
  5. How do you convolve modulo 10^9 + 7? Three NTT-friendly primes and the Chinese remainder theorem, or split each number into 15-bit halves and use a careful double FFT.
  6. How do you multiply n linear polynomials quickly? Divide and conquer: multiply the two halves recursively and combine with one NTT. O(n log² n). One at a time is O(n²).
  7. What does the coefficient of x^k in Π(1 + s_i x) count? The ways to choose k groups and one element from each: the elementary symmetric polynomial e_k of the s_i.
  8. How do you test an NTT? A stress test against the O(n·m) double loop on random small inputs with values right up to p − 1.

Glossary

Term Meaning Example
Modulus The number whose remainder we keep 998244353
Prime A number with no divisors except 1 and itself 7, 998244353
Modular inverse x⁻¹ with x · x⁻¹ ≡ 1 (mod p): division mod p 2⁻¹ = 4 mod 7
Fermat's little theorem x^(p−1) ≡ 1 mod a prime p (x ≠ 0), so x⁻¹ = x^(p−2) power(n, MOD - 2)
Primitive root A number whose powers visit every nonzero remainder 3 mod 7; 3 mod 998244353
Order How many jumps until the powers return to 1 order of 2 mod 7 is 3
Root of unity A number w with w^len = 1 2 is a 3rd root of unity mod 7
FFT Fast Fourier transform: O(n log n) evaluation at complex roots of unity episode 82
NTT Number theoretic transform: the FFT mod a prime, exact ntt(a, inv)
Convolution c[t] = Σ a[i] · b[t − i]: polynomial multiplication Sweet Boxes
Butterfly Two values in, u + w·v and u − w·v out the NTT's inner loop
Bit-reversal Reordering so index bits are reversed before the butterflies 3 (011) ↔ 6 (110)
Mantissa (53 bits) The precise digits of a double, about 16 decimal digits why the FFT is off by 21
Negative % In C++, −7 % p is −7 add MOD first
Divide and conquer Solve both halves, then combine prod(l, mid) · prod(mid, r)
Generating polynomial A polynomial whose coefficients count choices 1 + s·x for one club
Coefficient extraction Reading the coefficient of x^k as the answer c[k]
Fast exponentiation Power by repeated squaring, O(log e) multiplications power(b, e)
CRT Chinese remainder theorem: combine remainders mod several primes multiplying mod 10^9 + 7
Stress test Fast vs slow exact solution on random inputs all 300 tests passed

Summary

  • A double holds about 16 digits; convolution sums mod p reach about 10^23, so the FFT mod p gives wrong residues (998244325 instead of 998244346).
  • Modulo a prime there are integer roots of unity: with a primitive root g, g^((p−1)/len) has order len. 998244353 = 119·2^23 + 1 with g = 3 has one for every power of two up to 2^23.
  • The NTT is the FFT with w = 3^((p−1)/len), the inverse via Fermat (x^(p−2)), all in long long, exact. Write (u − v + MOD) % MOD.
  • Counting = multiplying: a choice per group is a small polynomial (1 + s·x), and the answer is a coefficient of the product.
  • Multiply many polynomials like a knockout bracket: O(n log² n). One at a time is O(n²).
  • Always stress test against the slow exact loop.

Solutions in C++, Java and Python

Problem N1 · Sweet Boxes

C++

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

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

Java

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

public class Main {
    static final long MOD = 998244353;

    static long power(long b, long e) {                  // fast exponentiation
        long r = 1;
        b %= MOD;
        for (; e > 0; e >>= 1, b = b * b % MOD)
            if ((e & 1) == 1) r = r * b % MOD;
        return r;
    }

    static void ntt(long[] a, boolean inv) {
        int n = a.length;
        for (int i = 1, j = 0; i < n; i++) {             // bit-reversed order
            int bit = n >> 1;
            for (; (j & bit) != 0; bit >>= 1) j ^= bit;
            j ^= bit;
            if (i < j) { long t = a[i]; a[i] = a[j]; a[j] = t; }
        }
        for (int len = 2; len <= n; len <<= 1) {
            long wl = power(3, (MOD - 1) / len);         // a len-th root of unity mod p
            if (inv) wl = power(wl, MOD - 2);            // the inverse root
            for (int i = 0; i < n; i += len) {
                long w = 1;
                for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                    long u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                    a[i + k] = (u + v) % MOD;
                    a[i + k + len / 2] = (u - v + MOD) % MOD;   // + MOD: never negative
                }
            }
        }
        if (inv) {
            long ninv = power(n, MOD - 2);               // divide by n
            for (int i = 0; i < n; i++) a[i] = a[i] * ninv % MOD;
        }
    }

    static long[] multiply(long[] a, long[] b) {
        int need = a.length + b.length - 1, n = 1;
        while (n < need) n <<= 1;
        long[] fa = Arrays.copyOf(a, n), fb = Arrays.copyOf(b, n);
        ntt(fa, false);
        ntt(fb, false);
        for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i] % MOD;
        ntt(fa, true);
        return Arrays.copyOf(fa, need);
    }

    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = (int) next(in), m = (int) next(in);
        long[] a = new long[n], b = new long[m];
        for (int i = 0; i < n; i++) a[i] = next(in);
        for (int i = 0; i < m; i++) b[i] = next(in);
        long[] c = multiply(a, b);
        StringBuilder out = new StringBuilder();
        for (long v : c) out.append(v).append(' ');
        System.out.println(out);
    }

    static long next(DataInputStream in) throws IOException {   // fast reader for 10^6 numbers
        int c = in.read();
        while (c != '-' && (c < '0' || c > '9')) c = in.read();
        boolean neg = c == '-';
        if (neg) c = in.read();
        long r = 0;
        for (; c >= '0' && c <= '9'; c = in.read()) r = r * 10 + (c - '0');
        return neg ? -r : r;
    }
}
1 998244346 874787574 246913578

Python

import sys

MOD = 998244353

def ntt(a, inv):
    n = len(a)
    j = 0
    for i in range(1, n):                       # bit-reversed order
        bit = n >> 1
        while j & bit:
            j ^= bit
            bit >>= 1
        j ^= bit
        if i < j:
            a[i], a[j] = a[j], a[i]
    length = 2
    while length <= n:
        wl = pow(3, (MOD - 1) // length, MOD)   # a len-th root of unity mod p
        if inv:
            wl = pow(wl, MOD - 2, MOD)          # the inverse root
        half = length // 2
        ws = [1] * half                         # powers of the root, computed once per level
        for k in range(1, half):
            ws[k] = ws[k - 1] * wl % MOD
        for i in range(0, n, length):
            for k in range(half):
                u = a[i + k]
                v = a[i + k + half] * ws[k] % MOD
                a[i + k] = (u + v) % MOD
                a[i + k + half] = (u - v) % MOD # Python's % is never negative
        length <<= 1
    if inv:
        ninv = pow(n, MOD - 2, MOD)             # divide by n
        for i in range(n):
            a[i] = a[i] * ninv % MOD

def multiply(a, b):
    need = len(a) + len(b) - 1
    n = 1
    while n < need:
        n <<= 1
    fa = a + [0] * (n - len(a))
    fb = b + [0] * (n - len(b))
    ntt(fa, False)
    ntt(fb, False)
    fa = [x * y % MOD for x, y in zip(fa, fb)]
    ntt(fa, True)
    return fa[:need]

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    a = [int(x) for x in data[2:2 + n]]
    b = [int(x) for x in data[2 + n:2 + n + m]]
    print(" ".join(map(str, multiply(a, b))))

main()
1 998244346 874787574 246913578

All three versions printed the same output on 5·10^5 + 5·10^5 random values. C++ took 0.24 s and Java 0.51 s, but pure Python took about 19 s: the Python version is correct, yet at the full limits it needs PyPy (or a C++ submission).

Problem N2 · Club Delegates

C++

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

const ll MOD = 998244353;

ll power(ll b, ll e) {                              // fast exponentiation, episode 21
    ll r = 1;
    b %= MOD;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1) r = r * b % MOD;
    return r;
}

void ntt(vector<ll>& a, bool inv) {
    int n = a.size();
    for (int i = 1, j = 0; i < n; i++) {            // bit-reversed order, as before
        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) {
        ll wl = power(3, (MOD - 1) / len);          // a len-th root of unity mod p
        if (inv) wl = power(wl, MOD - 2);           // the inverse root
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                ll u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                a[i + k] = (u + v) % MOD;
                a[i + k + len / 2] = (u - v + MOD) % MOD;
            }
        }
    }
    if (inv) {
        ll ninv = power(n, MOD - 2);                 // divide by n = multiply by n^-1
        for (auto& x : a) x = x * ninv % MOD;
    }
}

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    int need = a.size() + b.size() - 1, n = 1;
    while (n < need) n <<= 1;
    a.resize(n);
    b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, true);
    a.resize(need);
    return a;
}

vector<ll> prod(const vector<ll>& s, int l, int r) {   // (1 + s[l] x) ... (1 + s[r-1] x)
    if (r - l == 1) return {1, s[l] % MOD};
    int mid = (l + r) / 2;
    return multiply(prod(s, l, mid), prod(s, mid, r));   // two halves of equal size
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> s(n);
    for (auto& v : s) cin >> v;
    vector<ll> c = prod(s, 0, n);
    cout << (k <= n ? c[k] : 0) << "\n";
}

Java

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

public class Main {
    static final long MOD = 998244353;

    static long power(long b, long e) {                  // fast exponentiation
        long r = 1;
        b %= MOD;
        for (; e > 0; e >>= 1, b = b * b % MOD)
            if ((e & 1) == 1) r = r * b % MOD;
        return r;
    }

    static void ntt(long[] a, boolean inv) {
        int n = a.length;
        for (int i = 1, j = 0; i < n; i++) {             // bit-reversed order
            int bit = n >> 1;
            for (; (j & bit) != 0; bit >>= 1) j ^= bit;
            j ^= bit;
            if (i < j) { long t = a[i]; a[i] = a[j]; a[j] = t; }
        }
        for (int len = 2; len <= n; len <<= 1) {
            long wl = power(3, (MOD - 1) / len);         // a len-th root of unity mod p
            if (inv) wl = power(wl, MOD - 2);            // the inverse root
            for (int i = 0; i < n; i += len) {
                long w = 1;
                for (int k = 0; k < len / 2; k++, w = w * wl % MOD) {
                    long u = a[i + k], v = a[i + k + len / 2] * w % MOD;
                    a[i + k] = (u + v) % MOD;
                    a[i + k + len / 2] = (u - v + MOD) % MOD;   // + MOD: never negative
                }
            }
        }
        if (inv) {
            long ninv = power(n, MOD - 2);               // divide by n
            for (int i = 0; i < n; i++) a[i] = a[i] * ninv % MOD;
        }
    }

    static long[] multiply(long[] a, long[] b) {
        int need = a.length + b.length - 1, n = 1;
        while (n < need) n <<= 1;
        long[] fa = Arrays.copyOf(a, n), fb = Arrays.copyOf(b, n);
        ntt(fa, false);
        ntt(fb, false);
        for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i] % MOD;
        ntt(fa, true);
        return Arrays.copyOf(fa, need);
    }

    static long[] prod(long[] s, int l, int r) {         // (1 + s[l] x) ... (1 + s[r-1] x)
        if (r - l == 1) return new long[]{1, s[l] % MOD};
        int mid = (l + r) / 2;
        return multiply(prod(s, l, mid), prod(s, mid, r));   // two halves of equal size
    }

    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = (int) next(in), k = (int) next(in);
        long[] s = new long[n];
        for (int i = 0; i < n; i++) s[i] = next(in);
        long[] c = prod(s, 0, n);
        System.out.println(k <= n ? c[k] : 0);
    }

    static long next(DataInputStream in) throws IOException {   // fast reader for 10^6 numbers
        int c = in.read();
        while (c != '-' && (c < '0' || c > '9')) c = in.read();
        boolean neg = c == '-';
        if (neg) c = in.read();
        long r = 0;
        for (; c >= '0' && c <= '9'; c = in.read()) r = r * 10 + (c - '0');
        return neg ? -r : r;
    }
}
11

Python

import sys

MOD = 998244353

def ntt(a, inv):
    n = len(a)
    j = 0
    for i in range(1, n):                       # bit-reversed order
        bit = n >> 1
        while j & bit:
            j ^= bit
            bit >>= 1
        j ^= bit
        if i < j:
            a[i], a[j] = a[j], a[i]
    length = 2
    while length <= n:
        wl = pow(3, (MOD - 1) // length, MOD)   # a len-th root of unity mod p
        if inv:
            wl = pow(wl, MOD - 2, MOD)          # the inverse root
        half = length // 2
        ws = [1] * half                         # powers of the root, computed once per level
        for k in range(1, half):
            ws[k] = ws[k - 1] * wl % MOD
        for i in range(0, n, length):
            for k in range(half):
                u = a[i + k]
                v = a[i + k + half] * ws[k] % MOD
                a[i + k] = (u + v) % MOD
                a[i + k + half] = (u - v) % MOD # Python's % is never negative
        length <<= 1
    if inv:
        ninv = pow(n, MOD - 2, MOD)             # divide by n
        for i in range(n):
            a[i] = a[i] * ninv % MOD

def multiply(a, b):
    need = len(a) + len(b) - 1
    n = 1
    while n < need:
        n <<= 1
    fa = a + [0] * (n - len(a))
    fb = b + [0] * (n - len(b))
    ntt(fa, False)
    ntt(fb, False)
    fa = [x * y % MOD for x, y in zip(fa, fb)]
    ntt(fa, True)
    return fa[:need]

def prod(s, l, r):                              # (1 + s[l] x) ... (1 + s[r-1] x)
    if r - l == 1:
        return [1, s[l] % MOD]
    mid = (l + r) // 2
    return multiply(prod(s, l, mid), prod(s, mid, r))   # two halves of equal size

def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    s = [int(x) for x in data[2:2 + n]]
    c = prod(s, 0, n)
    print(c[k] if k <= n else 0)

main()
11

Both also print 0 on the edge case 3 5 / 2 3 1. On 200000 random clubs (k = 100000) all three print the same answer; C++ took 0.53 s and Java 0.70 s, while pure Python took about 29 s, so again use PyPy or C++ at the full limits.