The editorial says the complexity is $$$O(M \log M \log N)$$$. I would think one part is from $$$O(M \log M)$$$ FFT, but I don't get the $$$\log N$$$ part. The editorial just says that each 'element' (aka a $$$dp'_{(A_i)}$$$) is 'involved' in at most $$$O(\log N)$$$ calls. I understand this claim, but I don't see how it helps. The only conclusion that comes to mind is that we're doing $$$O(\log N)$$$ FFTs, but that doesn't seem to be the case.
I would say there are roughly $$$\frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \dots \approx n$$$ multiplications, so for me this would be $$$O(N M \log M)$$$.
Some time ago I also had this misconception in the complexity analysis in the editorial of a Codechef problem (you can also see the comments).
Basically, I want to know what I didn't understand, and why the complexity is actually $$$O(M \log M \log N)$$$.
PS: I made this blog because it seems there was no announcement (nor any discussion blog). Feel free to use it to discuss other problems too.
Nevermind, I understood it. I leave it in case it helps anyone.
It's a better upper bound thanks to the fact that the maximum degree in the polynomial products starts being rather small, and then grows as we do the products (we do not consider all products to be $$$O(M \log M)$$$ as I thought before). The degrees involving, e.g, $$$A_1$$$ would be $$$A_1 + A_2$$$, $$$A_1 + A_2 + A_3 + A_4$$$, $$$A_1 + \dots + A_8$$$, etc... We see each $$$A_i$$$ is involved at most $$$O(\log N)$$$ times. So we need to consider the sum of degrees in the complexity, and since this can be rearranged, it's the same as considering $$$(A_1 + \dots + A_N) \log N = M \log N$$$. Also, $$$M$$$ is an upper bound for any sum so we can just write $$$\log M$$$ for the FFT part, and that's how we get $$$O(M \log M \log N)$$$.