FFT

坑

---

NTT

坑

---

多项式求逆

也就是求$$ A(x)B(x) = 1 \pmod{x^n}$$

假设我们已知$$ A(x)G(x) = 1 \pmod{x^{\lceil{n \over 2}\rceil}} $$

两式相减得$$ A(x)(B(x) - G(x)) = 0 \pmod{x^{\lceil{n \over 2}\rceil}}$$

$$ B(x) - G(x) = 0 \pmod{x^{\lceil{n \over 2}\rceil}}$$

$$ B^2(x) + G^2(x) - 2B(x)G(x) = 0 \pmod{x^n}$$

两边同时乘上$A(x)$

$$ A(x)B^2(x) + A(x)G^2(x) = 2A(x)B(x)G(x) $$

因为$A(x)B(x) = 1$, 所以可以得到

$$ B(x) + A(x)G^2(x) = 2G(x) $$

$$ B(x) = 2G(x) - A(x)G^2(x) $$

当n = 1时，设A(x) = a, B(x) = inv(a)

就这样解决了

时间复杂度为$O(n \log n)$ $($别问我为什么我也不知道$)$

---

多项式开根

也就是求

$$ B^2(x) = A(x) \pmod{x^n} $$

假设我们已知$$ G^2(x) = A(x) \pmod{x^{\lceil{n \over 2}\rceil}} $$

两式相减得$$ B^2(x) - G^2(x) = 0 \pmod{x^{\lceil{n \over 2}\rceil}} $$

然后平方一下$$ B^4(x) + G^4(x) - 2B^2(x)G^2(x) = 0 \pmod{x^n} $$

$$ B^4(x) + G^4(x) = 2B^2(x)G^2(x) \pmod{x^n} $$

配一下方$$ B^4(x) + G^4(x) + 2B^2(x)G^2(x) = 4B^2(x)G^2(x) \pmod{x^n} $$

$$ (B^2(x) + G^2(x))^2 = (2B(x)G(x))^2 \pmod{x^n} $$

$$ B^2(x) + G^2(x) = 2B(x)G(x) \pmod{x^n} $$

因为$A(x)B(x) = 1$, 所以可以得到

$$ B(x) = {A(x) + G^2(x) \over {2G(x)}} $$

为了方便实现，我们常把它化成

$$ B(x) = {A(x) \over 2G(x)} + {G(x) \over 2} $$

当n = 1时，设B(x) = 1

然后就解决了

时间复杂度为$O(n \log n)$ $($别问我为什么我也不知道$)$