【Learning】多项式的一坨东西

## 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)$ $($别问我为什么我也不知道$)$