啖光之花加强版

题意

已知

现给出

解法1

是序列 的母函数,那么

再设

由于后者是一个 次多项式,那么卷积 的时候可以在 的意义下进行

代入 可以得到

现在的问题是如何快速对于所有 计算

构造

代入 可以得到

注意到(这里的 指在 意义下翻转多项式的前 项系数)

对比 的系数可以得到

那么只需要先分治 FFT 求出 ,然后求出 ,对 分别进行多点求值即可

复杂度