Has Not Appeared
0/8

# Introduction to Fast Fourier Transform

Authors: Benjamin Qi, Neo Wang

Quickly multiplying polynomials

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

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

## Solution - Convolution Mod

Resources
Benq

Notice that $c_i=\sum_{j=0}^i a_jb_{i-j}$ is the coefficient if we were to treat $a$ and $b$ as polynomials. Recall that $ax^jbx^{i-j}=abx^i$ is the coefficient of one multiplication that leads to $c_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 tightusing str = string; // yay python!
using vl = vector<ll>;using vi = vector<int>;


## Solution - Convolution Mod $10^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 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

StatusSourceProblem NameDifficultyTags
POIEasy
KattisEasy
KattisNormal
KattisVery Hard

### On a Tree

StatusSourceProblem NameDifficultyTags
YSHard
Show TagsCentroid, FFT
DMOJVery Hard
Show TagsCentroid, FFT

### 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!