我们说$B(x)$是$A(x)$在模$x^n$意义下的逆元则是满足
$$A(x)\ast B(x)\equiv1(mod \; x^n)$$
考虑分治
假如我们已经知道在模$x^{\lceil \frac{n}{2} \rceil}$下$A$的逆$B’$
对于两个多项式
$$A(x)=\sum_{i=0}^{N-1}a_ix^i$$
$$B(x)=\sum_{i=0}^{N-1}b_ix^i$$
FFT可以在$O(nlgn)$的时间内求出
$$C(x)=A(x)*B(x)=\sum_{i=0}^{2(N-1)}c_ix^i$$
其中$c_i=\sum_{j=0}^ia_jb_{i-j}$
PhoenixGS
Genius
Yuyao, China
文章
27
分类
0
标签
22
Update your browser to view this website correctly. Update my browser now
×