多项式一些基础的操作
- 多项式乘法
- 多项式求逆
- 多项式除法/取模
- 多项式牛顿迭代法
- 多项式开根
- 多项式 $\ln$
- 多项式 $\exp$
- 多项式 $k$ 次幂
- 多项式多点求值和快速插值
封装的代码可以看挑战多项式
写的时候要注意各种清空问题.
多项式乘法
略
时间复杂度$\mathcal O(n\log n)$
1 | const int P = 998244353; |
多项式求逆
给定多项式$A(x)$，求$A^{-1}(x)$满足$$A(x)A^{-1}(x)\equiv 1\pmod{x^n}$$
其中$\pmod{x^n}$即为舍去次数$\ge n$的项，只保留$0$到$n-1$次项
考虑倍增，或者直接套下面的牛顿迭代
$n=1$时只有常数项，答案可以直接快速幂求出
假设当前已经求出$\pmod{x^{\lceil \frac{n}{2} \rceil}}$意义下的$A(x)$的逆元$B_0(x)$，满足$$A(x)B_0(x)\equiv 1\pmod{x^{\lceil \frac{n}{2} \rceil}}$$
需要求$B(x)$满足$$A(x)B(x)\equiv 1\pmod{x^n}$$
两式相减得$$A(x)(B(x)-B_0(x))\equiv 0\pmod{x^{\lceil \frac{n}{2} \rceil}}$$
即$$B(x)-B_0(x)\equiv0\pmod{x^{\lceil \frac{n}{2} \rceil}}$$
平方得$$B^2(x)-2B(x)B_0(x)+B_0^2(x)\equiv0\pmod{x^n}$$
由于一个多项式平方之后，次数$<n$的项至少是由原先一个次数$<\lceil \frac{n}{2} \rceil$的项乘上其他项得到的，所以这个结果的$0$到$n-1$次系数仍然是$0$，可以变成$\pmod{x^n}$
同乘$A(x)$得$$B(x)-2B_0(x)+A(x)B_0^2(x)\equiv0\pmod{x^n}$$
即$$B(x)\equiv B_0(x)(2-A(x)B_0(x))\pmod{x^n}$$
时间复杂度$$T(n)=T(\frac{n}{2})+\mathcal O(n\log n)=\mathcal O(n\log n)$$
1 | inline void polyinv(int n, int *a, int *b){ |
多项式除法/取模
给定$n-1$次多项式$A(x)$和$m-1$次多项式$B(x)$，求$D(x)\ R(x)$满足$$A(x)=D(x)B(x)+R(x)$$
其中$D(x)$最高$n-m$次，$R(x)$次数$<m-1$
或$$A(x)\equiv R(x)\pmod{B(x)}$$
由于这里有余数$R(x)$难以处理，可以考虑去掉其影响
定义反转操作(将各项系数反转)$$A^R(x)=x^{n-1}A(\frac{1}{x})=\sum_{i=0}^{n-1}a_{n-i-1}x^i$$
把$\frac{1}{x}$代入原式，再同乘$x^{n-1}$，得到$$x^{n-1}A(\frac{1}{x})=x^{n-m}D(\frac{1}{x})x^{m-1}B(\frac{1}{x})+x^{n-m+1}*x^{m-2}R(\frac{1}{x})$$
即$$A^R(x)=D^R(x)B^R(x)+x^{n-m+1}R^R(x)$$
由于$D^R(x)$也是$n-m$次的，在$\pmod{x^{n-m+1}}$意义下，得到$$A^R(x)\equiv D^R(x)B^R(x)\pmod{x^{n-m+1}}$$
可以通过多项式求逆得到$D^R(x)$，反转即为$D(x)$，再代入计算$R(x)$
需要一次求逆和两次乘法
时间复杂度$\mathcal O(n\log n)$
1 | inline void polydiv(int n, int m, int *d, int *a, int *b, int *r){ |
多项式牛顿迭代法
这个好像可以用来推很多东西..
有一个关于多项式$f(x)$的方程$g(f(x))=0$
假设已经求出了$f(x)$的前$n$项$f_0(x)$
$$f(x)\equiv f_0(x)\pmod{x^n}$$
$$g(f_0(x))\equiv 0\pmod{x^n}$$
对$g(f(x))$在$f_0(x)$上泰勒展开
$$g(f(x))=g(f_0(x))+\frac{g’(f_0(x))}{1!}(f(x)-f_0(x))^1+\frac{g’’(f_0(x))}{2!}(f(x)-f_0(x))^2+·······$$
注意到$f(x)-f_0(x)$的前$n$项系数为$0$，于是
$$g(f(x))\equiv g(f_0(x))+g’(f_0(x))(f(x)-f_0(x))\equiv 0\pmod{x^{2n}}$$
即$$f(x)\equiv f_0(x)-\frac{g(f_0(x))}{g’(f_0(x))}\pmod{x^{2n}}$$
用这种方法也可以推多项式求逆
多项式开根
给定多项式$A(x)$,求$B(x)$满足$$B^2(x)-A(x)\equiv0\pmod{x^n}$$
设$B(x)\equiv B_0(x)\pmod{x^n}$，直接代入牛顿迭代
$$
\begin{aligned}
B(x)&\equiv B_0-\frac{B_0^2(x)-A(x)}{2B_0(x)} \
&\equiv\frac{1}{2}\left( B_0(x)+\frac{A(x)}{B_0(x)}\right)\pmod{x^{2n}}
\end{aligned}
$$
复杂度$$T(n)=T(\frac{n}{2})+\mathcal O(n\log n)=\mathcal O(n\log n)$$
若常数项不是很优秀，当$n=1$时，还需要计算二次剩余（我不会）
代码中常数项恰好为$1$
1 | inline void polysqrt(int n, int *a, int *b){ |
多项式$\ln$
对于一个多项式$A(x)$，求$$\ln(A(x))\pmod{x^n}$$
直接计算
$$
\begin{aligned}
&\ln(A(x)) \
=&\int (\ln(A(x)))’ \
=&\int\frac{A’(x)}{A(x)}
\end{aligned}
$$
其中的求导和积分都是可以$\mathcal O(n)$完成的
**需要保证$A(x)$常数项为$1$**，否则由于求导后常数项丢失，会出现一些问题
时间复杂度$\mathcal O(n\log n)$
1 | inline void polyln(int n, int *a, int *b){ |
多项式$\exp$
对于一个多项式$A(x)$，求$$e^{A(x)}\pmod{x^n}$$
设
$$B(x)\equiv e^{A(x)}\pmod{x^n}$$
两边取对数
$$
\begin{aligned}
\Longrightarrow & &\ln(B(x))&\equiv A(x)&\pmod{x^n} \
\Longrightarrow & &\ln(B(x))-A(x)&\equiv 0&\pmod{x^n}
\end{aligned}
$$
设$B(x)\equiv B_0(x)\pmod{x^n}$，得到递推式
$$
\begin{aligned}
B(x)&\equiv B_0(x)-\frac{\ln(B(x))-A(x)}{\frac{1}{B(x)}}&\pmod{x^{2n}} \
\Longrightarrow B(x)&\equiv B_0(x)(1-\ln(B_0(x))+A(x))&\pmod{x^{2n}}
\end{aligned}
$$
$A(x)$的常数项必须为$0$，$B(x)$常数项必定为$1$
我不知道为什么
复杂度$$T(n)=T(\frac{n}{2})+\mathcal O(n\log n)=\mathcal O(n\log n)$$
1 | void polyexp(int n, int *a, int *b){ |
多项式$k$次幂
给定多项式$f(x)$和正整数$k$，求$f^k(x)$的前$n$项系数
直接快速幂，复杂度$\mathcal O(n\log n\log k)$
当$f(x)$的常数项为$1$时，有$$f^k(x)=\exp(k\ ln(f(x)))$$
复杂度为$\mathcal O(n\log n)$
若$f(x)$的常数项不为1，设$f(x)$最低次项为$ax^d$，则$$f^k(x)=a^kx^{kd}\left(\frac{f(x)}{ax^d}\right)^k$$
可以用上面的方法计算