多项式小结

未完待续……

Orz great_influence

树套树每套一层就多一个log,但是多项式可以倍增随便套都可以分析得$O(n\log n)$,瑟瑟发抖

0. 定义

deg(F)表示F(x)的次数。

$F_r(x)=x^{deg(F)}F(\frac{1}{x})$也就是把系数反转。

1. 多项式乘法

就是FFT/NTT。传送门

2. 多项式求逆

给定$F(x)$,求$G(x)$使得$F(x)G(x)\equiv1\pmod {x^n}$

倍增。假设我们求出来了$G_1(x)$使得$F(x)G_1(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}}$
$$
G(x)-G_1(x)\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}\\
(G(x)-G_1(x))^2\equiv 0\pmod{x^n}\\
G^2(x)-2G(x)G_1(x)+G_1(x)\equiv 0\pmod{x^n}\\
F(x)(G^2(x)-2G(x)G_1(x)+G_1^2(x))\equiv 0\pmod{x^n}\\
G(x)-2G_1(x)+F(x)G_1^2(x)\equiv 0\pmod{x^n}\\
G(x)\equiv 2G_1(x)-F(x)G_1^2(x)\pmod{x^n}
$$
递归计算即可。根据主定理$T(n)=T(\frac{n}{2})+O(n\log n)=O(n\log n)$

3. 多项式除法

给定$F(x),G(x)$,求$Q(x),R(x)$使得$Q(x)G(x)+R(x)=F(x)$,其中$deg(R)<deg(G)$。

设$deg(F)=n,deg(G)=m$,则$deg(Q)=n-m,deg(R)=m-1$(r的高次补0)
$$
Q(x)G(x)+R(x)=F(x)\\
Q(\frac{1}{x})G(\frac{1}{x})+R(\frac{1}{x})=F(\frac{1}{x})\\
x^n(Q(\frac{1}{x})G(\frac{1}{x})+R(\frac{1}{x}))=x^n(F(\frac{1}{x}))\\
Q_r(x)G_r(x)+R_r(x)(x^{n-m+1})=F_r(x)
$$

由于$deg(Q)=n-m$,
$$
Q_r(x)G_r(x)\equiv F_r(x)\pmod{x^{n-m+1}}\\
Q_r(x)\equiv F_r(x)\cdot G_r^{-1}(x)\pmod{x^{n-m+1}}
$$
求逆乘完以后需要反转回来。

什么?R?直接$R=F-GQ$就可以了啊。

还是$O(n\log n)$

4. 多项式sqrt

给定$F(x)$,求$G(x)$使得$G^2(x)\equiv F(x)\pmod {x^n}$

还是倍增。假设求出来了$G_1(x)$使得$G_1^2(x)\equiv F(x)\pmod{x^{\lceil\frac{n}{2}\rceil}}$
$$
G(x)\equiv G_1(x)\pmod{x^{\lceil\frac{n}{2}\rceil}}\\
G(x)-G_1(x)\equiv 0 \pmod{x^{\lceil\frac{n}{2}\rceil}}\\
(G(x)-G_1(x))^2\equiv 0 \pmod {x^{\lceil\frac{n}{2}\rceil}}\\
G^2(x)-2G_1(x)G(x)+G_1^2(x)\equiv 0 \pmod{x^n}\\
F(x)-2G_1(x)G(x)+G_1^2(x)\equiv 0 \pmod{x^n}\\
G(x)\equiv \frac{F(x)+G_1^2(x)}{2G_1(x)}
$$

复杂度依然$O(n\log n)$

5. 多项式求导、积分

给定$F(x)$,求$F’(x)$和$\int F(x)$。

设$F(x)=\sum\limits_{i=0}^na_ix^i$,则$F’(x)=\sum_{i=1}^nia_ix^{i-1}$,$\int F(x)=\sum_{i=0}^n \frac{a_ix^{i+1}}{i+1}$

6. 多项式ln

给定$F(x)$,求$G(x)\equiv\ln F(x)\pmod {x^n}$。

由于$G’(x)=ln’ F(x)=\frac{F’(x)}{F(x)}$(链式法则),$G(x)=\int\frac{F’(x)}{F(x)}$。

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

7. 多项式牛顿迭代

给定$F$,求$G(x)$使得$F(G(x))\equiv 0\pmod {x^n}$

倍增。

已知$F(G_1(x))\equiv 0 \pmod{x^{\lceil\frac{n}{2}\rceil}}$。

在$G_1(x)$这点泰勒展开$F(G(x))=F(G_1(x))+\frac{F’(G_1(x))}{1!}(G(x)-G_1(x))+\frac{F’’(G_1(x))}{2!}(G(x)-G_1(x))^2+\cdots$。

显然$G(x)-G_1(x)\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}$

那么$(G(x)-G_1(x))^2\equiv \pmod{x^n}$,所以后面的项就不用管了。
$$
0\equiv F(G(x))\equiv F(G_1(x))+F’(G_1(x))(G(x)-G_1(x))\pmod{x^n}\\
F’(G_1(x))G(x)\equiv F’(G_1(x))G_1(x)-F(G_1(x))\pmod{x^n}\\
G(x)\equiv \frac{F’(G_1(x))G_1(x)-F(G_1(x))}{F’(G_1(x))}\equiv G_1(x)-\frac{F(G_1(x))}{F’(G_1(x))}\pmod{x^n}
$$
​ 时间复杂度仍然是$O(n\log n)$

8. 多项式exp

给定$F(x)$,求$G(x)\equiv e^{F(x)}\pmod{x^n}$。

显然$F(x)\equiv \ln G(x)\pmod {x^n}$

那么$\ln G(x)-F(x)\equiv 0\pmod {x^n}$。

设$H(G(x))=\ln(G(x))-F(x)$,显然$H’(G(x))\equiv \frac{1}{G(x)}\pmod{x^n}$。

牛顿迭代,直接可以得到$G(x)\equiv G’(x)(1-\ln G(x)+F(x))$。

时间复杂度当然还是$O(n\log n)$

9. 多项式幂次

给定$F(x),k$,求$G(x)\equiv F^k(x)\pmod{x^n}$

$F^k(x)=e^{k\ln F(x)}$,时间复杂度$O(n\log n)$

10. 例题

1.【模板】多项式乘法

FFT模板。

2.【模板】多项式求逆

求逆模板。

3.【模板】多项式除法

除法模板

4.CF438E 小朋友与二叉树

多项式开根。题解

5.【模板】多项式对数函数

多项式ln模板

6.【模板】多项式指数函数

多项式exp模板

7. COGS2189 帕秋莉的超级多项式

一个集合了大部分多项式操作的模板。

所有操作的模板以及这题的题解:

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
/*
Author: CNYALI_LK
LANG: C++
PROG: polynomial.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
namespace Polynomial{
const ll p=998244353,g_=3;
ll rev[266667];
ll fpm(ll a,ll b){
ll c=1;
while(b){
if(b&1)c=c*a%p;
a=a*a%p;
b>>=1;
}
return c;
}
void Rev(ll n,ll *f){
for(ll i=0;i<=n&&i<n-i;++i)swap(f[i],f[n-i]);
}
void NTT(ll *f,ll n,ll flag){
for(ll i=1;i<n;++i){
rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
if(i<rev[i])swap(f[i],f[rev[i]]);
}
for(ll i=1;i<n;i<<=1){
ll ww=fpm(g_,flag*((p-1)/(i+i))+p-1);
for(ll j=0;j<n;j+=i+i){
ll w=1,u,v;
for(ll k=0;k<i;++k){
u=f[j+k];v=f[j+k+i]*w%p;
f[j+k]=(u+v)%p;
f[j+k+i]=(u-v+p)%p;
w=w*ww%p;
}
}
}
if(!~flag){
ll in=fpm(n,p-2);
for(ll i=0;i<n;++i)f[i]=f[i]*in%p;
}
}
ll f1[266667],g1[266667];
void Mul(ll n,ll *f,ll m,ll *g,ll *h){//卷积
ll N=1;
while(N<=n+m)N<<=1;
for(ll i=0;i<N;++i){f1[i]=f[i];if(i>n)f[i]=0;}
for(ll i=0;i<N;++i){g1[i]=g[i];if(i>m)g[i]=0;}
NTT(f,N,1);
if(f!=g)NTT(g,N,1);
for(ll i=0;i<N;++i)h[i]=f[i]*g[i]%p;
NTT(h,N,-1);
if(f!=h){for(ll i=0;i<N;++i)f[i]=f1[i];}
if(g!=h){for(ll i=0;i<N;++i)g[i]=g1[i];}
}
/*
1: Inv
2: Div ln
3. Sqrt exp
4. Sqrt Pow
*/
ll h1[266667],h2[266667],h3[266667],h4[266667];
void Inv(ll n,ll *f,ll *g){//求逆
if(n==1){
g[0]=fpm(*f,p-2);
g[1]=g[2]=g[3]=0;
return;
}
else{
ll m=(n+1)>>1;
Inv(m,f,g);
ll N=1;
while(N<=n+m+m-3)N<<=1;
for(ll i=0;i<N;++i){f1[i]=f[i];if(i>=n)f[i]=0;if(i>=m)g[i]=0;}
NTT(f,N,1);
NTT(g,N,1);
for(ll i=0;i<N;++i)g[i]=(g[i]+g[i]-g[i]*g[i]%p*f[i]%p+p)%p;
NTT(g,N,-1);
for(ll i=0;i<N;++i)f[i]=f1[i];
for(ll i=n;i<N;++i)g[i]=0;
}
}
void Div(ll n,ll *f,ll m,ll *g,ll *q,ll *r){//除法
Rev(n,f);
Rev(m,g);
Inv(n-m+1,g,h2);
for(ll i=n-m+1;i<=n+n-m-m+2;++i)q[i]=0;
Rev(n,f);
Rev(m,g);
Rev(n-m,q);
Mul(m,g,n-m,q,r);
for(ll i=0;i<=n;++i){r[i]=(f[i]-r[i]+p)%p;}
}
void Sqrt(ll n,ll *f,ll *g){//开根
if(n==1){
g[0]=(ll)(sqrt(f[0])+0.5);
g[1]=0;
}
else{
ll m;
Sqrt(m=(n+1)>>1,f,g);
Mul(m-1,g,m-1,g,h3);
if(n-1>m+m-2)h3[n-1]=0;
for(ll i=0;i<n;++i)h3[i]=(h3[i]+f[i])%p;
for(ll i=0;i<m;++i)g[i]=g[i]*2%p;
Inv(n,g,h4);
Mul(n-1,h4,n-1,h3,g);
for(ll i=n;i<n+n;++i)g[i]=0;
}
}
ll inv[266667];
void Integ(ll n,ll *f,ll *g){//积分
inv[1]=1;
for(ll i=2;i<=n+1;++i)inv[i]=(p-p/i)*inv[p%i]%p;
for(ll i=n;~i;--i)g[i+1]=f[i]*inv[i+1]%p;
g[0]=0;
}
void Deriv(ll n,ll *f,ll *g){//求导
for(ll i=1;i<=n;++i)g[i-1]=f[i]*i%p;
g[n]=0;
}
void ln(ll n,ll *f,ll *g){//对数
Inv(n,f,h2);
Deriv(n-1,f,g);
Mul(n-1,h2,n-2,g,g);
for(ll i=n-1;i<=n+n-3;++i)g[i]=0;
Integ(n-2,g,g);
}
void exp(ll n,ll *f,ll *g){//指数
if(n==1){
g[0]=1;
g[1]=0;
}
else{
exp((n+1)>>1,f,g);
ln(n,g,h3);
for(int i=0;i<n;++i){
h3[i]=(f[i]-h3[i]+p)%p;
}
h3[0]=(h3[0]+1)%p;
Mul(n-1,h3,(n-1)>>1,g,g);
for(int i=n;i<n+n;++i)g[i]=0;
}
}
void Pow(ll n,ll *f,ll k,ll *g){//幂次
ln(n,f,h4);
for(ll i=0;i<n;++i)h4[i]=(h4[i]*k)%p;
exp(n,h4,g);
}
}
using namespace Polynomial;
ll f[266667],g[266667],h[266667];
int main(){
freopen("polynomial.in","r",stdin);
freopen("polynomial.out","w",stdout);
ll n,m,k;
n=read();
k=read();
for(ll i=0;i<n;++i)f[i]=read();
Sqrt(n,f,g);
Inv(n,g,f);
Integ(n-1,f,f);
f[n]=0;
exp(n,f,g);
Inv(n,g,f);
f[0]=(f[0]+1)%p;
ln(n,f,g);
g[0]=(g[0]+1)%p;
Pow(n,g,k,f);
Deriv(n-1,f,f);
for(ll i=0;i<n;++i)printf("%lld%c",f[i],i==n-1?'\n':' ');

return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×