暴力技巧.
有时候需要做多项式求逆, $\exp,\ln$ ,模数不是 NTT 模数,但多项式长度比较小,就不用写 MTT ,可以用暴力代替.
暴力 $\exp$
已知多项式 $A$ ,需要求出 $B=\exp(A)$ .
$$
B=\exp(A) \\
B’=\exp(A)\cdot A’\\
B’=B\cdot A’ \\
B=\int B\cdot A’
$$
求出 $B$ 的第 $i$ 项系数后,可以暴力卷积求出 $\int B\cdot A’$ 的第 $i$ 项系数,也就算出了 $B$ 的第 $i+1$ 项系数.
时间复杂度 $O(n^2)$ .
暴力多项式求逆
已知多项式 $A$ ,需要求出 $B=A^{-1}$ .
因为 $A\cdot B=1$ ,所以根据 $A$ 的系数和 $B$ 的前 $i-1$ 项系数可以直接解出 $B$ 的第 $i$ 项系数.
时间复杂度 $O(n^2)$ .
暴力 $\ln$
已知多项式 $A$ ,需要求出 $B=\ln A$ .
$$
B=\ln A\\
B’=\frac{A’}{A} \\
B=\int \frac{A’}{A}
$$
用暴力多项式求逆算出 $A^{-1}$ 即可,时间复杂度 $O(n^2)$ .