板子库里有Poly，所以写一下带项式的常数优化吧。摘抄自negiizhao的blog。
记号
长度\(n\)总是某个\(2^k\)。
\(\mathrm{E}(n)\)表示做长度为\(n\)的dft的时间。显然有\(\mathrm{E}(2n)=2\mathrm{E}(n)+O(n)\)，一般来说线性的部分我们可以忽略。
\(\mathrm{M}(n)\)表示做长度为\(n\)的普通卷积(答案长度是\(2n\))的时间，有\(\mathrm{M}(n)=6\mathrm{E}(n)+O(n)\)。
\(\mathcal{F}_l(F)\)表示\(F\)的长度为\(l\)的dft。
先补一点前置知识
我对多项式取模没什么感觉。可以结合线性递推来理解它。
比如说我们要求斐波那契数\(f_n\)，做法是把\(f_n\)展开变成\(f_{n-1}+f_{n-2}\)，然后把\(f_{n-1}\)展开变成\(f_{n-2}+f_{n-3}\)，不停展开最高次项，直到只剩下\(f_0\)和\(f_1\)。
你发现这个事情很好玩，它实际上是一个类似于竖式除法的过程，我们每次消掉最高的项。更进一步地，我们实际上是在用斐波那契数的特征多项式\(z^2-z-1\)去除\(z^n\)。
所以说，对一个多项式取模，实际上是描述了每一项对低次一些的项的贡献。把这个除数多项式的最高次项系数变为\(-1\)，后面的系数就直接变成了贡献的系数。
然而这个前置知识好像没啥用，尽管我以为它会有用（
倒数 inv
要求\(G=\frac{1}{F}\)，朴素的迭代式是\(G\equiv G_0-(FG_0-1)G_0\equiv 2G_0-FG_0^2\pmod{z^{2n}}\)。
直接做，每轮需要\(\mathrm{M}(n)\)计算\(G_0^2\)，\(\mathrm{M}(2n)\)计算\(FG_0^2\)，总共就是\(18\mathrm{E}(n)\)。这是等比数列求和，所以总的还是\(18\mathrm{E}(n)\)(为什么不是\(36\)?因为我们最后一次是从\(\frac{n}{2}\)迭代到\(n\))。
考虑\(G\equiv G_0-(FG_0-1)G_0\pmod{z^{2n}}\)这个式子，注意到\((F\bmod{z^{2n}})G_0-1\)的长度是在\(3n\)以内的，并且它的\(0\)到\(n-1\)次项必然是\(0\)，所以我们实际上可以用长度为\(2n\)的循环卷积计算这个东西，循环卷积中溢出的部分恰好是\(0\)到\(n-1\)次，我们把这一段清零即可。
同理，\(((FG_0-1)\bmod{z^{2n}})G_0\)的长度是在\(3n\)以内的，它的\(0\)到\(n-1\)次项也必然是\(0\)，所以也只需要长度为\(2n\)的循环卷积。这样总共需要\(6\mathrm{E}(2n)=12\mathrm{E}(n)\)。
注意到其中有两次对\(G_0\)的长度为\(2n\)的dft，可以省略一次，总共是\(10\mathrm{E}(n)\)。
除法/对数 div/ln
给\(F,H\)，令\(G=1/F\)，要求\(Q=\frac{H}{F}=HG\)。对数和除法只差\(O(n)\)。
直接做就是\(10\mathrm{E}(n)\)求出\(G\)，然后硬乘，总共是\(16\mathrm{E}(n)\)。
考虑用牛迭展开\(Q\bmod{z^{2n}}\)，有\(Q\equiv Q_0-(FQ_0-H)G_0\pmod{z^{2n}}\)。
可以用上面的倒数，\(10\mathrm{E}(n)\)求出\(G_0\)，然后用\(6\mathrm{E}(n)\)求出\(Q_0\equiv H_0G_0\pmod{z^n}\)。
然后两次乘法的性质和倒数基本相同，用倒数中的方法\(12\mathrm{E(n)}\)即可计算\((FQ_0-H)G_0\)。总共是\(28\mathrm{E}(n)\)。具体地，\((F\bmod{z^{2n}})Q_0-H\)长度不超过\(3n\)，阶至少是\(n\)，所以可以用长为\(2n\)的循环卷积计算，\((((F\bmod{z^{2n}})Q_0-H)\bmod{z^{2n}})G_0\)是一样的。
注意到我们求\(Q_0\)的时候已经对\(G_0\)做了长为\(2n\)的dft，所以可以省去一次，变成\(26\mathrm{E}(n)\)，于是做长度为\(n\)的除法就需要\(13\mathrm{E}(n)\)。
平方根 sqrt
给\(F\)，求\(G^2=F\)。
令\(H=\frac{1}{G}\)，迭代式为\(G\equiv G_0-\frac{(G_0^2-F)H_0}{2}\pmod{z^{2n}}\)。
直接做就是每轮一次\(10\mathrm{E}(n)\)的倒数，然后需要\(\mathrm{M}(n)+\mathrm{M}(2n)\)的乘法，总共是\(28\mathrm{E}(n)\)。
考虑一个牛逼做法，我们牛迭算\(H_0\)，它满足方程\(FH^2-1=0\)，迭代式为\(H\equiv H_0-\frac{FH_0^3-H_0}{2}\pmod{z^{2n}}\)。注意到\(FH_0^3-H_0\)的长度不超过\(5n\)，阶至少是\(n\)，可以用长度为\(4n\)的循环卷积计算，需要\(12\mathrm{E}(n)\)。于是算\(H\bmod{z^n}\)总共需要\(12\mathrm{E}(n)\)。这一步同时搞定了\(\mathcal{F}_{2n}(F\bmod{z^n})\)。
然后还是使用\(G\)的迭代式\(G\equiv G_0-\frac{(G_0^2-F)H_0}{2}\pmod{z^{2n}}\)。
容易知道\(G_0=FH_0\)，而前面算了\(\mathcal{F}_{2n}(F\bmod{z^n})\)，于是爆算是\(4\mathrm{E}(n)\)的。这一步同时搞定了\(\mathcal{F}_{2n}(H_0)\)。
注意到\(G_0^2-F\)的阶至少是\(n\)，于是计算可以用长\(n\)的循环卷积计算，需要\(2\mathrm{E}(n)\)。
注意到\((G_0^2-F)H_0\)的长度不超过\(3n\)，阶至少是\(n\)，可以用长\(2n\)的循环卷积计算，而我们已经拿到了\(\mathcal{F}_{2n}(H_0)\)，所以只需要\(4\mathrm{E}(n)\)。
这总共是\(22\mathrm{E}(n)\)的，于是长度为\(n\)的平方根需要\(11\mathrm{E}(n)\)。
指数 exp
重头戏（
有些人的exp比别人的inv还快（
给\(F\)，求\(G=\exp F\)。
令\(H=\frac{1}{G}\)，直接做，迭代式为
\[G\equiv G_0-G_0\left(\int G_0^\prime H_0-F\right)\pmod{z^{2n}}\]，调用一次\(26\mathrm{E}(n)\)的除法，一次长\(4n\)的乘法，需要\(38\mathrm{E}(n)\)。不过如果你用爆力的方法，调用一次\(36\mathrm{E}(n)\)的逆，一次长\(2n\)的乘法，一次长\(4n\)的乘法，会变成\(54\mathrm{E}(n)\)。
有一个简单方法可以做到\(16.5\mathrm{E}(n)\)。我看不懂论文哥在写啥，但是论文好像讲的还可以¿
大概是说，我们迭代时维护\(G\bmod{z^n}\)和\(H\bmod{z^{\frac{n}{2}}}\)。\(H\)满足方程\(HG-1=0\)，于是迭代式是\(H\equiv H_0-\frac{H_0G_0-1}{G_0}\equiv 2H_0-G_0H_0^2\pmod{z^n}\)。这个式子就是倒数的式子，可以在\(6\mathrm{E}(n)\)内计算。这里并不能使用倒数的技巧，是因为结果前面只有\(\frac{n}{2}\)项是\(0\)。
还需要一点技巧，如果我们知道了一个多项式的\(\mathcal{F}_n\)，计算\(\mathcal{F}_{2n}\)只需要\(E(n)\)的时间，因为dft实际上是一组点值，法法塔本质上是分治。我们考虑少了的那一部分，实际上只需要先代入一次本原单位根\(\omega_{2n}\)更新系数，然后做dft即可。最后把两边做一层dft合并起来，这是线性的。所以在刚才的计算中，如果我们已经保留了\(\mathcal{F}_{n}(G_0)\)，则只需要\(5\mathrm{E}(n)\)的时间，而这是可以做到的。
然后我们搞定了\(H\)，考虑\(G\)的迭代式，我们把它改写成
\[G\equiv G_0+G_0\left(F-\int(F^\prime+H(G_0^\prime-G_0F^\prime))\right)\pmod{z^{2n}}\]首先可以看到有一个\(\int\)，所以\(\int\)里面的东西的长度只需要保留到\(2n-1\)。
。注意到最里面是一个\(\exp\)求导的形式，也就是\((\exp(F))^\prime=\exp(F)F^\prime\)，所以\(G_0^\prime-G_0F^\prime\)长度不超过\(2n-1\)，且前\(n-1\)项都是\(0\)(这里的\(-1\)实现时要注意)，可以用长\(n\)的循环卷积计算，需要\(3\mathrm{E}(n)\)，而我们已经计算了\(\mathcal{F}_{2n}(G_0)\)，可以类似倍长做到线性的法法塔折半，所以只需要\(2\mathrm{E}(n)\)。dif-dit实现的法法塔，这里需要计算两个bitrev，所以还挺要命的（
然后是\(H\)乘上那个东西，它的长度不超过\(3n-1\)，且前\(n-1\)项都是\(0\)，还是可以用长\(2n\)的循环卷积计算，需要\(6\mathrm{E}(n)\)，并且这一步计算了下一轮需要用到的\(\mathcal{F}_{2n}(H)\)。
然后是\(G_0\)乘上那个大括号，它的长度不超过\(3n\)，且前\(n\)项都是\(0\)，还是可以用长\(2n\)的循环卷积计算，刚才已经计算了\(\mathcal{F}_{2n}(G_0)\)所以只需要\(4\mathrm{E}(n)\)。
总共是\(17\mathrm{E}(n)\)。因为我们并不需要计算\(H\)，所以可以在最后一次迭代中去掉相关的计算，就得到\(16.5\mathrm{E}(n)\)，不过我认为如果不想实现法法塔倍长(实际上也不困难)，\(18\mathrm{E}(n)\)实在是速度不慢(和爆力的倒数一样快)又好写(然而实际上啥都不好写)（
边界可能比较麻烦，一个解决方法是从\(l=2\)开始迭代，因为我们知道有\([z]G=[z]F\)，或者说\(G,F\)的一次项是相等的。
实现的话，可以看我的 板子库，实现了10E(n) inv, 13E(n) ln/div, 11E(n) sqrt, 12E(n) inv_sqrt, 18E(n) exp。