题解：P4721 【模板】分治 FFT

· · 题解

多项式求逆

化简原始式子

F = FG + f_0x^0 \pmod{x^n} F = FG + 1 \pmod{x^n} F(1-G) = 1 \pmod{x^n} F = (1-G)^{-1} \pmod{x^n}

直接多项式求逆即可。

int n;
poly f, g;
signed main(){
    n = rd() - 1, g = get(n);
    g[0] = 1;
    for (int i = 1; i <= n; i++) g[i] = (P - rd()) % P;
    f = inv(g, n);
    for (int i = 0; i <= n; i++) printf ("%d ", f[i]);
    return 0;
}

分治 NTT

好吧，言归正传，这题是分治 NTT 板子，我们考虑用分治做，用类似于 cdq 分治优化 dp 的思路来做。

首先假设分治区间为 [l,r]。

  1. 分治处理 [l,mid] 的 f 值。
  2. 处理 [l,mid] 对 [mid+1,r] 的 f 的影响。
  3. 分治 [mid+1,r]。

关键是第 2 步，就是求下面的式子。

w_k = \sum_{i=l}^{mid} f_{i}g_{k-i}

可以直接 NTT 做到 O(n\log n)，最后主定理算一下就是 O(n\log^2n) 的。

void solve(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    solve(l, mid), h = get(n);
    for (int i = l; i <= mid; i++) h[i] = f[i];
    h = mod(h * g, n + 1);
    for (int i = mid + 1; i <= r; i++) f[i] = (f[i] + h[i]) % P;
    solve(mid + 1, r);
}

然后就 T 了。毕竟常数太大了，我们来优化一下。

优化很简单，我们发现前面为 0 的位置没有用，直接位移一下即可。

void solve(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    solve(l, mid), h = get(mid - l), t=  get(r - l);
    for (int i = l; i <= mid; i++) h[i - l] = f[i];
    for (int i = 1; i <= r - l; i++) t[i] = g[i];
    h = h * t;
    for (int i = mid + 1; i <= r; i++) f[i] = (f[i] + h[i - l]) % P;
    solve(mid + 1, r);
}
signed main(){
    n = rd() - 1, f = g = get(n);
    for (int i = 1; i <= n; i++) g[i] = rd();
    f[0] = 1, solve(0, n);
    for (int i = 0; i <= n; i++) printf ("%d ", f[i]);
    return 0;
}