## § Vandermonde and FFT

FFT lets you do the following: You are given two sequences: a0,...,an and b0,...,bm Compute sequence c0,…,c[n+m] such that
$c[i]=a[0]b[i]+a[1]b[i−1]+ \dots +a[i−1]b[1]+a[i]b[0]$
This is exactly what I needed here, where $a[i]= \binom{n}{i}$ and $b[i]= \binom{m}{i}$. If I thought for a little longer I would realize that $c[i]=\binom{n+m}{i}$ instead of computing it using FFT.

#### § References

• [Codeforces contest comment by Swistakk) [https://codeforces.com/blog/entry/85348?#comment-730898 ]