A Universe of Sorts

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

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