上一篇博客(指支配树)还没有写完,结果就要开始写这篇博客……
其实是
复习预习笔记了
以下内容都是在取模意义下,默认模数 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
128namespace POLY{
const int MOD=998244353,G=3;
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 山遥路远-网易云