【Learning】 多项式的相关计算
约定的记号
对于一个多项式\(A(x)\)，若其最高次系数不为零的项是\(x^k\)，则该多项式的次数为\(k\).
记为\(deg(A)=k\).
对于\(x\in(k,+ \infty)\)，称\(x\)都为\(A(x)\)的次数界. 但一般地，我们都使用\(k+1\)作为\(A(x)\)的次数界。
多项式求逆
给定多项式\(A(x)\)，求其在模\(x^n\)意义下的逆多项式\(B(x)\)，使得
\[
\begin{equation} \label{eqn1} A(x)B(x)\equiv1 \pmod {x^n} \end{equation}
\]
其中，\(B(x)\)的次数小于等于\(A(x)\)的次数.
采用倍增思路向上倍增求解.
当\(n=1\)时，\(A(x)\)与\(B(x)\)仅有一个常数项，且\(B(x)\)的常数项为\(A(x)\)常数项的逆元。多项式有无逆元也取决于这个常数是否有逆元.
假设已经求得\(A(x)\)在模\(x^{\lceil\frac n 2\rceil}\)意义下的逆元\(B'(x)\)。
\[
\begin{equation} A(x)B'(x)=1 \pmod{x^{\lceil\frac n 2\rceil}} \end{equation}
\]
而\((1)\)放在模\(x^{\lceil\frac n 2\rceil}\)意义下同样成立，有
\[
\begin{equation} \label{eqn2} A(x)B(x)\equiv1 \pmod {x^{\lceil\frac n 2\rceil}} \end{equation}
\]
将\((3)-(2)\)得到
\[
B(x)-B'(x)\equiv 0 \pmod {x^{\lceil\frac n 2\rceil}}
\]
平方得到
\[
B^2(x)-2B(x)B'(x)+B’^2(x)\equiv 0 \pmod {x^n}
\]
模数同时平方的原因是：原本多项式模\(x^{\lceil\frac n 2\rceil}\)为0，说明\(0\)~\(\lceil\frac n 2\rceil-1\)项的系数为0，平方后由于系数相乘，这些0系数会导致0~n-1项系数为0，也即模\(x^n\)为0.
两边同乘\(A(x)\)，消去\(B(x)\)并移项，得到
\[
B(x) \equiv 2B'(x) – A(x)B’^2(x) \pmod {x^n}
\]
至此可以递归倍增求解，伪代码如下，忽略清零、取模操作。
void polyInv(int *a,int *b,int n){ // a是要求逆元的多项式，b是在模x^n意义下的a的逆元
if(n==1) 令b为一个次数为1,常数项为a[0]的逆元的多项式，返回;
polyInv(a,b,(n+1)>>1);
ntt_init(dega+degb+degb); //ntt长度
static int A[]=a,B[]=b; //临时数组，防止影响到传入的指针
ntt(A);
ntt(B);
for(int i=0;i<nttlen;i++)
A[i]=2*B[i]-A[i]*B[i]*B[i]; //点值计算
ntt(A,-1);
b=A;
}
时间复杂度\(O(n log n)\)，不过我不知道怎么证.
多项式除法及取模
给定多项式\(A(x)\)和多项式\(B(x)\)，求两个多项式\(D(x)\)与\(R(x)\)，使得
\[
\begin{equation} \label{1} A(x)=D(x)B(x)+R(x) \end{equation}
\]
其中，\(deg(A)>=deg(B)\) , \(deg(D)\leq deg(A)-deg(B)\)，\(deg(R)<deg(B)\).
除法用奇妙变化解决.
引入一个操作：翻转操作. 对于一个次数为\(n\)的多项式\(A(x)\)，定义
\[
A^R(x)=x^nA(\frac 1 x)
\]
会发现\(A^R(x)\)的系数相对于\(A(x)\)完全\(reverse\)了一下。
将\((4)\)的\(x\)换成\(\frac 1 x\)，并两边同乘\(x^n\)，记\(n=deg(A)\), \(m=deg(B)\), \(deg(D)=n-m\), \(deg(R)=m-1\).
\[
\begin{aligned}
x^nA(\frac1x)&=x^{n-m}D(\frac1x)x^mB(\frac1x)+x^{n-m+1}x^{m-1}R(\frac1x)\\
A^R(x)&=D^R(x)B^R(x)+x^{n-m+1}R^R(x)
\end{aligned}
\]
我们发现\(D^R(x)\)的次数仍然等于\(n-m\)，如果把上式放在模\(x^{n-m+1}\)意义下，我们会发现\(D^R(x)\)不会受到任何影响，而\(x^{n-m+1}R^R(x)\)被完全模掉了！
于是
\[
\begin{aligned}
A^R(x)&\equiv D^R(x)B^R(x)\pmod{x^{n-m+1}}\\
D^R(x)&\equiv A^R(x){B^R}^{-1}(x)\pmod{x^{n-m+1}}
\end{aligned}
\]
直接对\(A\)系数翻转，\(B\)系数翻转，求\(B\)的逆，\(A\)和\(B\)一乘，把结果的系数再次翻转，就是\(D\)了！
void polyDiv(int *a,int *b,int *d){// a和b对应上文的A和B，d是上文的D，是答案
if(deg(a)<deg(b)) 令d为一个0多项式，返回;
reverse(a);
reverse(b);
static int invb[];
polyInv(b,invb,deg(b)+1); //b次数界是deg(b)+1
d=a*invb;
reverse(d);
}
如果你还要求\(R(x)\)，带回最初的式子直接算就好，多项式乘法用*直接代替了。
void polyMod(int *a,int *b,int *r){
if(deg(a)<deg(b)) 令r为a，返回;
static int d[];
polyDiv(a,b,d);
r=a-d*b;
}