[多项式算法]多项式求逆 学习笔记 |
您所在的位置：网站首页 › 多项式逆元怎么计算 › [多项式算法]多项式求逆 学习笔记 |
|
多项式求逆
和整数的乘法逆元定义类似，对于多项式\(A(x)B(x)=1\)，则称\(A(x),B(x)\)互为乘法逆元。 \(A(x)\)存在乘法逆元的充要条件是\([x^0]A(x)\)存在乘法逆元。 现在思考如何用\(O(n\log n)\)的时间计算\(A(x)\)的乘法逆元： 考虑倍增，当前已求出前\(n\)项的逆元，则：\(A(x)B(x)\equiv 1\pmod{x^n}\) \[\begin{equation} \begin{split} A(x)B(x)-1&\equiv 0\pmod{x^n}\\ \Big(A(x)B(x)-1\Big)^2&\equiv0\pmod{x^{2n}}\\ A(x)^2B(x)^2-2A(x)B(x)+1&\equiv 0\pmod{x^{2n}}\\ 2A(x)B(x)-A(x)^2B(x)^2&\equiv1\pmod{x^{2n}}\\ A(x)B(x)\Big(2-A(x)B(x)\Big)&\equiv1\pmod{x^{2n}}\\ \end{split} \end{equation} \]这样我们就能求出\(\mod{x^{2n}}\)下的逆元：\(B(x)\Big(2-A(x)B(x)\Big)\)，重复\(O(\log n)\)次即可得到答案。 时间复杂度：\(T(n)=T(\frac n2)+O(n\log n)=O(n\log n)\) 代码：例题：P4238 【模板】多项式求逆 //Luogu-O2 #include #include #include #include #include #define rint register int typedef long long ll; #define Getchar (p1==p2&&(p2=(p1=In)+fread(In,1,1 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |