Introduction to Fast Fourier Transform

Tutorial

Solution - Convolution Mod

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.

Copy
#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 $10^9+7$

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

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

On a Tree