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

## Tutorial

Resources | ||||
---|---|---|---|---|

cp-algo | Implementation | |||

CSA | ||||

CF | ||||

CF | also see Pt 2 |

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

## $10^9+7$

Solution - Convolution ModResources | ||||
---|---|---|---|---|

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

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

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