不一样的单 log 分治 FFT

普通分治 fft 是两个 log 的且常数较大。而多项式求逆是一个 log 的但是在一些比较复杂的分治 fft 任务中更加难想——例如，分治 fft 是多维的，转移为 \(f_{p}*trans_{p,q}\to f_{q}\)。

我们发现普通分治 fft 还要递归右边是十分麻烦的，但是注意洛谷的分治 fft 模板题，下标是连续的，所以右边的转移方式和左边一样，故其实可以直接乘上左边的多项式。

综上，不需要再递归右边，复杂度变为 \(O(n\log n)\)。

当然，你可能注意到上面这个过程写成代码后和生成函数求分治 fft 的过程几乎一样。但是也是一种更方便的理解，不是吗。

void solve(int l, int r, poly &f, poly &g, const poly &G) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    solve(l, mid, f, g, G);
    g.resize(r - l + 1);
    for (int i = mid - l + 1; i <= r - l; i++) g[i] = G[i];
    poly tmp = f * g;
    for (int i = 0; i <= mid - l; i++) tmp[i] = 0;
    tmp = tmp * f;
    f.resize(r - l + 1);
    for (int i = mid - l + 1; i <= r - l; i++) f[i] = tmp[i];
}
int main() {
    int n;
    scanf("%d", &n);
    poly g(n), f = {1}, tmp;
    for (int i = 1; i < n; i++) scanf("%d", &g[i]);
    solve(0, n - 1, f, tmp, g);
    for (int i = 0; i < n; i++) printf("%d ", f[i]);
}