题解：P4721 【模板】分治 FFT

· · 题解

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

先随便揪出一篇题解看看：

每次把区间分为左右两半，先算左半段，然后用 fft 计算左半段对右半段的贡献，再算右半段。

我们发现普通分治 fft 还要递归右边是十分麻烦的，但是注意洛谷的分治 fft 模板题，下标是连续的，所以右边的转移方式和左边一样，故其实可以这么做：用 fft 计算出左半段对右半段的贡献，保留右半段，再直接乘上左边的多项式，把右半段与原本的左半段拼起来就是答案。

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

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]);
}