长期项目多项式系列

legendgod

2021-03-07 07:12:32

Personal

$Update \ on \ 2021.4.6:$ 用封装更新了大部分的 NTT,修改了 Exp $Update \ on \ 2021.4.1:

修改了 将求逆进行函数化,更新了多项式 \ln 的上界

Update\ on \ 2021.3.29:

修改了 NTT 和求逆元,增加了定义。

笔者基本上会将所有的函数中的上界,表示为该多项式的次数是多少。

因为极其严格的上界要求可以让我们减少调试。

\color{red}FFT \text{入门感悟}

\color{red} NTT \text{ 初探}

\color{red}MTT\text{ 初探}

\color{red}NTT \text{ 多项式求逆元}

\color{red}MTT \text{ 任意模数求多项式逆元}

\color{red}\text{多项式对数函数,多项式} \ln

\color{red}\text{多项式指数函数,多项式} \exp

这里做一个小总结,现在的 代码 可以支持加减乘除和以上等操作,都是在膜 998244353 的意义下,如果想要更改模数,可以直接在 const 那里更改,注意要把原根也改了哦!

更加优秀的代码

\color{red}\text{多项式开根}

\color{red}\text{伪 分治 FFT}

\color{red}\text{多项式除法 初探}

\color{red}\text{常系数齐次线性递推}

\color{red}\text{Berlekamp-Massey,BM 算法}