多项式全家桶

多项式乘法逆

链接

先说几个简单性质：

1. $f\equiv g\pmod {x^n}$ $\Rightarrow$ $\forall i\in [0,n], f\equiv g\pmod {x^i}$。
2. $f\equiv g\pmod {x^n}$ $\Rightarrow$ $f^k\equiv g^k\pmod {x^{kn}}$。

开始操作。

$$f\times g\equiv 1\pmod {x^{\lceil\frac{n}{2}\rceil}}$$ $$f\times h\equiv 1\pmod {x^n}\Leftrightarrow f\times h\equiv 1\pmod {x^{\lceil\frac{n}{2}\rceil}}$$ $$f\times g-f\times h\equiv 0 \pmod {x^{\lceil\frac{n}{2}\rceil}}$$ $$g-h\equiv 0 \pmod{x^{\lceil\frac{n}{2}\rceil}}$$ $$(g-h)^2\equiv 0\pmod{x^{2\times\lceil\frac{n}{2}\rceil}}\Leftrightarrow(g-h)^2\equiv 0\pmod{x^n}$$ $$g^2-2g h+h^2\equiv 0 \pmod {x^n}$$ 左右两边乘上 $f$ $$g^2f-2g(h\times f)+h\times(h\times f)\equiv 0 \pmod{x^n}$$ $$h\equiv 2g-g^2f$$

多项式ln函数

多项式ln函数
首先$B\equiv \ln A \pmod {x^n}$
我们两边同时取导 $B^{-1} \equiv \ln^{-1} A\pmod {x^n}$
根据小学二年级的知识:

$$B' \equiv \frac{A'}{A}\pmod {x^n}$$ $$B'=A' A^{-1}\pmod {x^n}$$

根据

$$f(x)=\sum _{i=0}^{n}a_ix^i$$ $$f'(x)=\sum_{i=0}^{n-1}(i+1)\times a_{i+1}\times x^i$$

我们很容易通过 $A$ 得出 $A’$ ;也很容易根据 $A’$ 得出 $A$。
所以本题可以使用多项式求逆后 $NTT$ 一次切了。