多项式小结

未完待续……

Orz great_influence

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

0. 定义

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

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

1. 多项式乘法

就是FFT/NTT。传送门

2. 多项式求逆

给定F(x)F(x),求G(x)G(x)使得

倍增。假设我们求出来了G1(x)G_1(x)使得

递归计算即可。根据主定理T(n)=T(n2)+O(nlogn)=O(nlogn)T(n)=T(\frac{n}{2})+O(n\log n)=O(n\log n)

3. 多项式除法

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

deg(F)=n,deg(G)=mdeg(F)=n,deg(G)=m,则deg(Q)=nm,deg(R)=m1deg(Q)=n-m,deg(R)=m-1(r的高次补0)

由于deg(Q)=nmdeg(Q)=n-m

求逆乘完以后需要反转回来。

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

还是O(nlogn)O(n\log n)

4. 多项式sqrt

给定F(x)F(x),求G(x)G(x)使得

还是倍增。假设求出来了G1(x)G_1(x)使得

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

5. 多项式求导、积分

给定F(x)F(x),求F(x)F'(x)F(x)\int F(x)

F(x)=i=0naixiF(x)=\sum\limits_{i=0}^na_ix^i,则F(x)=i=1niaixi1F'(x)=\sum_{i=1}^nia_ix^{i-1}F(x)=i=0naixi+1i+1\int F(x)=\sum_{i=0}^n \frac{a_ix^{i+1}}{i+1}

6. 多项式ln

给定F(x)F(x),求

由于G(x)=lnF(x)=F(x)F(x)G'(x)=ln' F(x)=\frac{F'(x)}{F(x)}(链式法则),G(x)=F(x)F(x)G(x)=\int\frac{F'(x)}{F(x)}

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

7. 多项式牛顿迭代

给定FF,求G(x)G(x)使得

倍增。

已知

G1(x)G_1(x)这点泰勒展开F(G(x))=F(G1(x))+F(G1(x))1!(G(x)G1(x))+F(G1(x))2!(G(x)G1(x))2+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

显然

那么 ,所以后面的项就不用管了。

​ 时间复杂度仍然是O(nlogn)O(n\log n)

8. 多项式exp

给定F(x)F(x),求

显然

那么

H(G(x))=ln(G(x))F(x)H(G(x))=\ln(G(x))-F(x),显然

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

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

9. 多项式幂次

给定F(x),kF(x),k,求

Fk(x)=eklnF(x)F^k(x)=e^{k\ln F(x)},时间复杂度O(nlogn)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;
}
文章目录
  1. 1. 0. 定义
  2. 2. 1. 多项式乘法
  3. 3. 2. 多项式求逆
  4. 4. 3. 多项式除法
  5. 5. 4. 多项式sqrt
  6. 6. 5. 多项式求导、积分
  7. 7. 6. 多项式ln
  8. 8. 7. 多项式牛顿迭代
  9. 9. 8. 多项式exp
  10. 10. 9. 多项式幂次
  11. 11. 10. 例题
    1. 11.1. 1.【模板】多项式乘法
    2. 11.2. 2.【模板】多项式求逆
    3. 11.3. 3.【模板】多项式除法
    4. 11.4. 4.CF438E 小朋友与二叉树
    5. 11.5. 5.【模板】多项式对数函数
    6. 11.6. 6.【模板】多项式指数函数
    7. 11.7. 7. COGS2189 帕秋莉的超级多项式
|

博客使用Disqus作为评论系统