I remember reading this problem in some contest, but I don't remember where. I think the contest was 2016 or so. I searched on a few websites with no luck. Do you happen to know what contest it was?

The problem is: Given integers *a*_{1}, ..., *a*_{n}, We define *x*_{0} = 1 and for every . Find *x*_{n}. The solution was *O*(*n* * *polylog*(*n*)) with FFT.

Is it Kyoya and Train's solution?

I remember 2 such problems from CSacademy: Colored Forests and Jetpack. Both are basically some easy combinatorics + what you're asking for.

Jetpack was the one I'm looking for, thanks!

I wrote this task on Codechef as well (late 2014): task / solution (It is like O(n log^2 n))

I saw you wrote a very detailed editorial. It must have taken lots of time.

Compliments.