Of course there's a Fast Fourier Transform problem in this contest! There may be number theory involved!

vector<int> f(int n)

You may assume $1\le n\le {10}^6$ - though in practice there is only one test case, so maybe you can guess the value of $n$ beforehand!