PrevNext
Has Not Appeared
 0/8

Introduction to Fast Fourier Transform

Authors: Benjamin Qi, Neo Wang

Quickly multiplying polynomials

Edit This Page

Focus Problem – try your best to solve this problem before continuing!

Focus Problem – try your best to solve this problem before continuing!

Tutorial

Solution - Convolution Mod

Resources
Benq

Notice that ci=j=0iajbijc_i=\sum_{j=0}^i a_jb_{i-j} is the coefficient if we were to treat aa and bb as polynomials. Recall that axjbxij=abxiax^jbx^{i-j}=abx^i is the coefficient of one multiplication that leads to cic_i. Thus, summing this up, we get the coefficient of each number of the polynomial. Since this happens to be the exact purpose of FFT, we can simply use our favorite FFT implementation to solve this problem.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python!
using vl = vector<ll>;
using vi = vector<int>;

Solution - Convolution Mod 109+710^9+7

Resources
Benq

NTT with three different moduli

Notice that this is the exact same problem as Convolution Mod, so simply changing the mod suffices.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python!
using vl = vector<ll>;
using vi = vector<int>;

Note - FFT Killer

The "multiplication with arbitrary modulus" described in cp-algo requires long double to pass.

Problems

StatusSourceProblem NameDifficultyTags
POIEasy
KattisEasy
KattisNormal
KattisVery Hard

On a Tree

StatusSourceProblem NameDifficultyTags
YSHard
Show TagsCentroid, FFT
Back to SchoolVery Hard
Show TagsCentroid, FFT

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext