关于本题时间复杂度问题

这道题的时间复杂度不应该是倍增的 $O(\log{n})$ 乘上 FFT/NTT 的时间复杂度 $O(n\log{n})$ 为 $O(n\ log^2{n})$ 吗？