标签：log pmod 多项式 全家 dfrac 2m deg

【多项式求逆】

【整式取模】

定义单项式取模。

\[C\cdot x^k\bmod x^n=\begin{cases}0&k\ge n\\C\cdot x^k&k<n\end{cases} \]

定义多项式取模为它的每一项取模相加。

可以看出，模 \(x^n\) 相当于保留 \(0\sim n-1\) 次项。

【问题描述】

一般形式：已知多项式 \(A(x),C(x)\)，求 \(B(x)\) 使 \(A(x)B(x)=C(x)\pmod {x^n}\)。

特殊形式：已知多项式 \(A(x)\)，求 \(D(x)\) 使 \(A(x)D(x)=1\pmod {x^n}\)。

我们只需要解特殊形式，因为解出特殊形式的 \(D(x)\) 后，可以令 \(B(x)=D(x)C(x)\)，一次卷积 \(O(n\log n)\) 即可。

【解法 - \(O(n^2)\)】

已知 \(A(x)\)，求 \(B(x)\) 使 \(A(x)B(x)=1\pmod {x^n}\)。

记 \(A,B\) 的系数为 \(A_0\sim A_{n-1},B_0\sim B_{n-1}\)。

首先要保证 \(A_0\neq 0\)，否则 \(A(x)\) 不可逆；然后可得 \(A_0B_0=1\)，可以解 \(B_0\)。

然后 \(A_1B_0+A_0B_1=0\)，可以解出 \(B_1\) …… 如此循环，可以 \(O(n^2)\) 求解。

【解法 - \(O(n\log n)\)】

注意到如果 \(A(x)B(x)=1\pmod {x^n}\)，则 \(A(x)B(x)=1\pmod {x^{n-1}}\)。所以我们可以增大 \(n\)，这样的解也是符合要求的解。

令 \(n=2^k\)，方便我们用倍增的方法优化。
假设已知 \(B(x)\) 满足 \(A(x)B(x)=1\pmod {x^m}\)，怎么求得 \(B_2(x)\) 满足 \(A(x)B_2(x)=1\pmod {x^{2m}}\)？

\[\begin{aligned} AB-1&=0\pmod {x^m}\\ (AB-1)^2&=0\pmod {x^{2m}}\\ A^2B^2-2AB+1&=0\pmod {x^{2m}}\\ 2AB-A^2B^2&=1\pmod {x^{2m}}\\ A(2B-AB^2)&=1\pmod {x^{2m}}\\ \end{aligned} \]

因此 \(B_2(x)=2B(x)-A(x)B(x)^2\)。从 \(A(x),B(x)\) 到 \(B_2(x)\)，只需要做两次多项式乘法和一次多项式减法，复杂度 \(O(n\log n)\)。
但是倍增也有一个 \(\log\) 啊？怎么是 \(O(n\log n)\) 呢？

因为对于一个 \(m\)，我们只保留多项式前 \(m\) 项即可，不用保留 \(n\) 项。因此复杂度应该是 \(O(n\log n+\frac{n}{2}\log n+\frac{n}{4}\log n+\cdots)=O(n\log n)\)。

【多项式带余除法】

给定 \(A(x),B(x)\)，找 \(C(x),R(x)\) 使得 \(A(x)=B(x)C(x)+R(x)\)，要求 \(\deg R(x)<\deg B(x)\)。
不妨 \(\deg A\ge\deg B\)，不然直接令 \(C(x)=0,R(x)=A(x)\)。记 \(n=\deg A,m=\deg B\)。

定义一个操作 \(R\)，\(A^R(x)=x^nA(\dfrac{1}{x})\)。
\(A^R\) 的作用其实就是把 \(A\) 的系数翻转（Reverse）了。可以手算一下。

\[\begin{aligned} A(x)&=B(x)C(x)+R(x)\\ A(\dfrac{1}{x})&=B(\dfrac{1}{x})C(\dfrac{1}{x})+R(\dfrac{1}{x})\\ x^nA(\dfrac{1}{x})&=x^nB(\dfrac{1}{x})C(\dfrac{1}{x})+x^nR(\dfrac{1}{x})\\ \end{aligned} \]

标签：log,pmod,多项式,全家,dfrac,2m,deg
From： https://www.cnblogs.com/FLY-lai/p/18147173