§ 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[i1]++a[i1]b[1]+a[i]b[0]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]=(ni)a[i]= \binom{n}{i} and b[i]=(mi)b[i]= \binom{m}{i}. If I thought for a little longer I would realize that c[i]=(n+mi)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 ]