多项式求逆
多项式求逆元
已知一度数为n的多项式\(A(x)\)。
\[A(x)B(x)\equiv1\pmod {x^n} \]\(B(x)\)即为\(A(x)\)的逆元。
多项式的除法、\(\exp\)和\(\ln\)都是基于多项式求逆的。
通常用倍增法处理多项式求逆问题。
开始推式子……
\[\begin{aligned} &AB'\equiv1\pmod {x^{\lceil\frac n 2\rceil}}\\ &A(B-B’)\equiv 0 \pmod {x^{\lceil\frac n 2\rceil}}\\ &B-B’\equiv 0 \pmod {x^{\lceil\frac n 2\rceil}}\\ &(B-B’)^2\equiv 0 \pmod {x^n}\\ &B^2+B'^2-2BB'\equiv 0 \pmod {x^n}\\ &A(B^2+B'^2-2BB')\equiv 0 \pmod {x^n}\\ &B-2B'+AB'^2\equiv 0 \pmod {x^n}\\ &B\equiv 2B'-AB'^2\pmod {x^n}\\ &B\equiv B'(2-AB')\pmod {x^n}\\ \end{aligned} \]这样我们可以从\(x^n\)递归到\(x^0\)。
使用NTT加速运算，复杂度\(O(n \log n)\)。
ll qp(ll d,ll c)
{
ll res=1;
while(c)
{
if(c&1) res=d*res%mod;
d=d*d%mod,c>>=1;
}
return res;
}
void ntt(ll *a,int type)
{
for(int i=0;i>1]>>1)|((i&1)<<(bit-1));
for(int i=0;i