学习笔记 - 多项式小结 | Lucky_Glass's Blog
0%

学习笔记 - 多项式小结

上一篇博客(指支配树)还没有写完,结果就要开始写这篇博客……

其实是复习预习笔记了

以下内容都是在取模意义下,默认模数 998244353,用快速数论变换NTT。


# 求逆

点击展开/折叠问题

给定 $n-1$ 次多项式 $A(x)$,求 $n-1$ 次多项式 $B(x)$,满足 $A(x)\cdot B(x)\equiv1\pmod{x^n}$

我们考虑递归的求解问题——

首先 $A(x)$ 在模 $x$ 意义下的逆元显然就是 $a_0$ 的逆元;

令 $m=\left\lceil\frac n2\right\rceil$,假设我们已经知道了 $A(x)$ 在模 $x^m$ 意义下的逆元为 $C(x)$,$C(x)$ 是一个 $m-1$ 次的多项式。

由于 $A(x)\cdot B(x)\equiv 1\pmod{x^n}$,那么也一定有 $A(x)\cdot B(x)\equiv1\pmod{x^m}$;

又有 $A(x)\cdot C(x)\equiv1\pmod{x^m}$,两式相减可得 $A(x)\cdot[B(x)-C(x)]\equiv 0\pmod{x^m}$。

因为 $A(x)$ 必然有常数项(否则无解),所以 $A(x)\not\equiv0\pmod{x^m}$,则 $B(x)-C(x)\equiv0\pmod{x^m}$。也就是说 $B(x)-C(x)$ 的前 $m$ 位均为 0,则 $[B(x)-C(x)]^2$ 的前 $n$($2m$)位也为 0,即:

递归求解即可。


# 带余除法

点击展开/折叠问题

给定 $n$ 次多项式 $A(x)$、$m$ 次多项式 $B(x)$($n\ge m$),求 $n-m$ 次多项式 $P(x)$、$m-1$ 次多项式 $Q(x)$,使得 $A(x)=B(x)\cdot P(x)+Q(x)$

由于 $x$ 只是一个形式变量,我们可以把它随便换成别的东西,比如:

记一个多项式 $A(x)$ 翻转过后得到的多项式为 $A_r(x)$。

则有:

反转一遍可以得到 $P(x)$,再得到 $Q(x)=A(x)-B(x)\cdot P(x)$。


# Ln()

点击展开/折叠问题

给出 $n$ 次多项式 $A(x)$,求模 $x^n$ 意义下的 $\ln A(x)$。

(不太会积分、求导……只有搬一下别人的博客)推一下式子(如果你会求导和积分)

然后再积分回来就好了。


# EXP

点击展开/折叠问题

给出 $n-1$ 次多项式 $A(x)$,求模 $x^n$ 意义下的 $e^{A(x)}$

要用到牛顿迭代……虽然我仍然不太会。

牛顿迭代用于近似求解方程 $f(x)=0$。

首先有泰勒展开:

那么牛顿迭代取前两项(关于 $x$ 线性)为 $f(x)$ 的近似,即 $f(x_0)+f’(x_0)(x-x_0)=0$,可以得到一次迭代解 $x_1=x_0-\frac{f(x_0)}{f’(x_0)}$,经过若干次迭代可以得到 $n$ 次迭代解。每迭代一次,所得近似解的精度翻倍

那么如何把牛顿迭代运用到 EXP 上?我们发现我们相当于要求 $B(x)$:

令所得多项式为 $P(B(x))$:

根据牛顿迭代,可以得到

根据导数的法则 $P’(x)=\frac{1}{B(x)}$,则有

考虑到每次迭代,所得解精度会翻倍。也就是说我们知道模 $x^n$ 的解,迭代一次就知道模 $x^{n/2}$ 的解。又因为在模 $x$ 意义下,$B(x)=1$,所以可以递归求解。


# 开根

点击展开/折叠问题

给定 $n-1$ 次多项式 $A(x)$,求在模 $x^n$ 次意义下 $\sqrt{A(x)}$。

题目一般会保证 $A(x)$ 常数项为 1,因为在模 998244353 意义下,一个数开根并不好做……

考虑递归求解,模 $x$ 意义下,$B(x)=1$。

设 $m=\left\lceil\frac{n}{2}\right\rceil$, $C^2(x)\equiv A(x)\pmod{x^m}$;

因为 $B^2(x)\equiv A(x)\pmod{x^n}$,那么一定有 $B^2(x)\equiv A(x)\pmod{x^m}$。

则有 $B(x)\equiv C(x)\pmod{x^m}$,两边平方,可以得到 $B^2(x)-2B(x)C(x)+C^2(x)\equiv 0\pmod{x^n}$,即 $A(x)-2B(x)C(x)+C^2(x)\equiv 0\pmod{x^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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
namespace POLY{
const int MOD=998244353,G=3;
#define cs const int &
#define clean(A,l,r) std::fill(A+(l),A+(r),0)
inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(cs a,cs b){return 1ll*a*b%MOD;}
inline int Pow(int a,int b){int r=1;for(;b;b>>=1,a=Mul(a,a))if(b&1)r=Mul(r,a);return r;}
int rev[N],powg[30],invg[30],lg2[N],inv[N];
int tmp1[N],tmp2[N],tmp3[N];
void Init(int siz){
for(int i=2;i<=siz;i++) lg2[i]=lg2[i>>1]+1;
for(int i=0;i<=20;i++) powg[i]=Pow(G,(MOD-1)>>i),invg[i]=Pow(powg[i],MOD-2);
inv[1]=1;
memset(tmp1,0,sizeof tmp1);
memset(tmp2,0,sizeof tmp2);
int nprn=0;
for(int i=2;i<=siz;i++){
if(!tmp1[i]) tmp2[++nprn]=i,inv[i]=Pow(i,MOD-2);
for(int j=1;j<=nprn && tmp2[j]*i<=siz;j++){
tmp1[tmp2[j]*i]=true;
inv[tmp2[j]*i]=Mul(inv[i],inv[tmp2[j]]);
if(i%tmp2[j]==0) break;
}
}
}
inline void NTT(int *A,cs len,cs typ){
int lgl=lg2[len];
register int i,j;
for(i=1;i<len;i++){
rev[i]=rev[i>>1]>>1|((i&1)<<(lgl-1));
if(i<rev[i]) std::swap(A[i],A[rev[i]]);
}
for(register int l=2,t=1,lgn=1;l<=len;l<<=1,lgn++,t<<=1){
int per=typ==1?powg[lgn]:invg[lgn];
for(j=i=0;i<len;j=(i+=l))
for(int cur=1;j<i+t;j++,cur=Mul(cur,per)){
int tmp=Mul(cur,A[j+t]);
A[j+t]=Sub(A[j],tmp);
A[j]=Add(A[j],tmp);
}
}
if(typ==1) return;
int invn=inv[len];
for(i=0;i<len;i++) A[i]=Mul(A[i],invn);
}
void Copy(int *A,int *B,cs len){for(register int i=0;i<len;i++) B[i]=A[i];}
void InvPoly(int len,int *A,int *B){
if(len==1){B[0]=Pow(A[0],MOD-2);return;}
InvPoly((len+1)>>1,A,B);
int Len=1;
while(Len<(len<<1)) Len<<=1;
static int tmp[N];
Copy(A,tmp,len),clean(tmp,len,Len);
clean(B,(len+1)>>1,Len);
NTT(tmp,Len,1),NTT(B,Len,1);
for(register int i=0;i<Len;i++) B[i]=Mul(Sub(2,Mul(tmp[i],B[i])),B[i]);
NTT(B,Len,-1);
clean(B,len,Len);
}
void Divide(int *A,cs n,int *B,cs m,int *Q,int *P){
Copy(A,tmp1,n),Copy(B,tmp2,m);
std::reverse(tmp1,tmp1+n),std::reverse(tmp2,tmp2+m);
clean(tmp2,n-m+1,m),clean(tmp1,n-m+1,n);
InvPoly(n-m+1,tmp2,Q);
int len=1;
while(len<2*(n-m+1)) len<<=1;
NTT(tmp1,len,1),NTT(Q,len,1);
for(register int i=0;i<len;i++) Q[i]=Mul(tmp1[i],Q[i]);
NTT(Q,len,-1);
std::reverse(Q,Q+n-m+1),clean(Q,n-m+1,len);
len=1;while(len<=n*2) len<<=1;
Copy(Q,tmp1,len),Copy(B,tmp2,len);
NTT(tmp1,len,1),NTT(tmp2,len,1);
for(register int i=0;i<len;i++) P[i]=Mul(tmp1[i],tmp2[i]);
NTT(P,len,-1);
for(register int i=0;i<m-1;i++) P[i]=Sub(A[i],P[i]);
}
void Derv(int *A,int *B,cs len){
for(int i=0;i<len-1;i++) B[i]=Mul(A[i+1],i+1);
B[len-1]=0;
}
void Inte(int *A,int *B,cs len){
for(int i=1;i<=len;i++) B[i]=Mul(inv[i],A[i-1]);
B[0]=0;
}
void Ln(int *A,int len,int *B){
memset(tmp2,0,sizeof tmp2);
Derv(A,tmp1,len);
InvPoly(len,A,tmp2);
int Len=1;
while(Len<len*2) Len<<=1;
clean(tmp1,len,Len),clean(tmp2,len,Len);
NTT(tmp1,Len,1),NTT(tmp2,Len,1);
for(int i=0;i<Len;i++) tmp1[i]=Mul(tmp1[i],tmp2[i]);
NTT(tmp1,Len,-1),clean(tmp1,len-1,Len);
Inte(tmp1,B,len-1);
}
void EXP(int len,int *A,int *B){
if(len==1){B[0]=1;return;}
EXP((len+1)>>1,A,B);
Ln(B,len,tmp3);
for(int i=0;i<len;i++) tmp3[i]=Sub(A[i],tmp3[i]);
tmp3[0]=Add(tmp3[0],1);
int Len=1;
while(Len<(len<<1)) Len<<=1;
clean(tmp3,len,Len),NTT(tmp3,Len,1);
clean(B,len,Len),NTT(B,Len,1);
for(int i=0;i<Len;i++) B[i]=Mul(B[i],tmp3[i]);
NTT(B,Len,-1);
clean(B,len,Len);
}
void Sqrt(int len,int *A,int *B){
if(len==1){B[0]=1;return;}
Sqrt((len+1)>>1,A,B);
int Len=1;
while(Len<(len<<1)) Len<<=1;
Copy(B,tmp3,len),clean(tmp3,len,Len);
InvPoly(len,tmp3,B),clean(B,len,Len);
NTT(tmp3,Len,1);
for(int i=0;i<Len;i++) tmp3[i]=Mul(tmp3[i],tmp3[i]);
NTT(tmp3,Len,-1),clean(tmp3,len,Len);
for(int i=0;i<len;i++) tmp3[i]=Add(tmp3[i],A[i]);
NTT(tmp3,Len,1),NTT(B,Len,1);
for(int i=0;i<Len;i++) B[i]=Mul(Mul(B[i],tmp3[i]),inv[2]);
NTT(B,Len,-1),clean(B,len,Len);
}
}

THE END

Thanks for reading!

> Linked 山遥路远-网易云