Introduction to Fast Fourier Transform
Authors: Benjamin Qi, Neo Wang
Quickly multiplying polynomials
Tutorial
Resources | |||||
---|---|---|---|---|---|
cp-algo | Implementation | ||||
CSA | |||||
CF | |||||
CF | also see Pt 2 |
Focus Problem – try your best to solve this problem before continuing!
Resources | |||||
---|---|---|---|---|---|
Benq |
Solution - Convolution Mod
Notice that is the coefficient if we were to treat and as polynomials. Recall that is the coefficient of one multiplication that leads to . 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.
Implementation
#include <bits/stdc++.h>using namespace std;using ll = long long;using db = long double; // or double, if TL is tightusing str = string; // yay python!using vl = vector<ll>;using vi = vector<int>;
Focus Problem – try your best to solve this problem before continuing!
Resources | |||||
---|---|---|---|---|---|
Benq | NTT with three different moduli |
Solution - Convolution Mod
Notice that this is the exact same problem as Convolution Mod, so simply changing the mod suffices.
Implementation
#include <bits/stdc++.h>using namespace std;using ll = long long;using db = long double; // or double, if TL is tightusing 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
Status | Source | Problem Name | Difficulty | Tags | ||
---|---|---|---|---|---|---|
POI | Easy | |||||
Kattis | Easy | |||||
Kattis | Normal | |||||
Kattis | Very Hard |
On a Tree
Status | Source | Problem Name | Difficulty | Tags | ||
---|---|---|---|---|---|---|
YS | Hard | Show TagsCentroid, FFT | ||||
Back to School | Very 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!