0%

多项式一些基础的操作

  • 多项式乘法
  • 多项式求逆
  • 多项式除法/取模
  • 多项式牛顿迭代法
  • 多项式开根
  • 多项式 $\ln$
  • 多项式 $\exp$
  • 多项式 $k$ 次幂
  • 多项式多点求值和快速插值

封装的代码可以看挑战多项式

写的时候要注意各种清空问题.


多项式乘法

时间复杂度$\mathcal O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int P = 998244353;
inline int Pow(ll x, int y=P-2){
ll ass=1;
for(; y; y>>=1, x=x*x%P) if(y&1) ass=ass*x%P;
return ass;
}
inline int Mod(int x){ return x<P?x:x-P;}
inline void NTT(int *f, int g){
for(int i=0, j=0; i<p; ++i){
if(i>j) swap(f[i], f[j]);
for(int k=p>>1; (j^=k)<k; k>>=1);
}
for(int i=1; i<p; i<<=1){
int w0=(g==1?Pow(3, (P-1)/i/2):Pow(Pow(3, (P-1)/i/2)));
for(int j=0; j<p; j+=i<<1){
int w=1;
for(int k=j; k<j+i; ++k){
int t=(ll)w*f[k+i]%P;
f[k+i]=Mod(P+f[k]-t);
f[k]=Mod(f[k]+t);
w=(ll)w*w0%P;
}
}
}
if(g==-1) for(int i=0, I=Pow(p); i<p; ++i) f[i]=(ll)f[i]*I%P;
}

多项式求逆

给定多项式$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
2
3
4
5
6
7
8
9
10
11
inline void polyinv(int n, int *a, int *b){
if(n==1) return (void)(b[0]=Pow(a[0]));
polyinv((n+1)/2, a, b);
static int tmp[N];
for(p=1; p<n*2-1; p<<=1);
memcpy(tmp, a, n<<2), memset(tmp+n, 0, p-n<<2);
NTT(tmp, 1), NTT(b, 1);
for(int i=0; i<p; ++i) b[i]=(2-(ll)b[i]*tmp[i]%P+P)*b[i]%P;
NTT(b, -1);
memset(b+n, 0, p-n<<2);
}

多项式除法/取模

给定$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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void polydiv(int n, int m, int *d, int *a, int *b, int *r){
static int A[N], B[N], B1[N];
memset(A, 0, sizeof A), memset(B, 0, sizeof B), memset(B1, 0, sizeof B1);

for(int i=0; i<n; ++i) A[i]=a[n-i-1];
for(int i=0; i<m; ++i) B[i]=b[m-i-1];
polyinv(n-m+1, B, B1);
for(p=1; p<n*2-m; p<<=1);
NTT(A, 1), NTT(B1, 1);
for(int i=0; i<p; ++i) d[i]=(ll)A[i]*B1[i]%P;
NTT(d, -1), memset(d+n-m+1, 0, p-(n-m+1)<<2);
for(int i=0, j=n-m; i<j; ++i, --j) swap(d[i], d[j]);

for(p=1; p<n; p<<=1);
for(int i=0; i<m; ++i) B[i]=b[i];
for(int i=0; i<n-m+1; ++i) B1[i]=d[i]; memset(B1+n-m+1, 0, p-(n-m+1)<<2);
NTT(B, 1), NTT(B1, 1);
for(int i=0; i<p; ++i) r[i]=(ll)B[i]*B1[i]%P;
NTT(r, -1);
for(int i=0; i<n; ++i) r[i]=(P+a[i]-r[i])%P;
}

多项式牛顿迭代法

这个好像可以用来推很多东西..

有一个关于多项式$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
2
3
4
5
6
7
8
9
10
11
12
inline void polysqrt(int n, int *a, int *b){
if(n==1) return (void)(b[0]=1);
polysqrt(n+1>>1, a, b);
static int tmp[N], b1[N];
polyinv(n, b, b1);
for(p=1; p<n*2-1; p<<=1);
memcpy(tmp, a, n<<2), memset(tmp+n, 0, p-n<<2);
NTT(tmp, 1), NTT(b, 1), NTT(b1, 1);
for(int i=0; i<p; ++i) b[i]=((ll)tmp[i]*b1[i]+b[i])%P*inv2%P;
NTT(b, -1);
memset(b+n, 0, p-n<<2), memset(b1, 0, p<<2);
}

多项式$\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
2
3
4
5
6
7
8
9
10
11
inline void polyln(int n, int *a, int *b){
static int tmp[N];
polyinv(n, a, b);
for(int i=1; i<n; ++i) tmp[i-1]=(ll)a[i]*i%P;
for(p=1; p<n*2-1; p<<=1);
NTT(tmp, 1), NTT(b, 1);
for(int i=0; i<p; ++i) b[i]=(ll)tmp[i]*b[i]%P;
NTT(b, -1);
for(int i=n-1; i; --i) b[i]=(ll)b[i-1]*Pow(i)%P;
b[0]=0, memset(b+n, 0, p-n<<2);
}

多项式$\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
2
3
4
5
6
7
8
9
10
11
12
void polyexp(int n, int *a, int *b){
if(n==1) return (void)(b[0]=1);
polyexp(n+1>>1, a, b);
static int tmp[N];
polyln(n, b, tmp);
for(int i=0; i<n; ++i) tmp[i]=Mod(!i+P+a[i]-tmp[i]);
for(p=1; p<n*2-1; p<<=1);
NTT(tmp, 1), NTT(b, 1);
for(int i=0; i<p; ++i) b[i]=(ll)b[i]*tmp[i]%P;
NTT(b, -1);
memset(b+n, 0, p-n<<2), memset(tmp, 0, p<<2);
}

多项式$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$$

可以用上面的方法计算


多点求值和快速插值

参考多项式多点求值和快速插值学习笔记