置顶-「OI之路」目录

「OI之路」目录(之前找起来太麻烦了)

另外把板子库也放在这里了

如你所见,很多东西只是个脉络,文章没写什么,相反教程链接更多

算是某些学习笔记吧,但并不是教程,也没有按难度顺序(但数学一章是按我推荐的顺序的),可以理解为一个框架:)
可以把它当做一个教程的合集,通常会给出一些不错的链接以及自己的一些学习笔记

应该写的最nb的文章就是:「OI之路」03数学-16快乐计数「OI之路」03数学-13生成函数次之

类似定位的东西是OI-wiki,可以配合食用

近期非修锅更新日志

2020.4 :带权二分

2020.5 :给多项式全家桶补充了$O(n^2)$递推方法

2020.6 :整改反演容斥、自然数幂和

语法与STL

个人认为熟练使用STL是一个OIer走向成熟的标志
「OI之路」01语法与STL-1概要与常识
「OI之路」01语法与STL-2STL
「OI之路」01语法与STL-3操作符和优先级
「OI之路」01语法与STL-4原码反码补码
「OI之路」01语法与STL-5二叉树

电脑操作知识备忘

数据结构

这里涉及东西比较多,但基本没什么教程,要自行学习(相当于列出一些药学的东西)
「OI之路」02数据结构-1分块与莫队
「OI之路」02数据结构-2树状数组
「OI之路」02数据结构-3伸展树
「OI之路」02数据结构-4树上启发式合并
「OI之路」02数据结构-5-kdtree
「OI之路」02数据结构-6主席树
「OI之路」02数据结构-7 LCT
「OI之路」02数据结构-8线段树,这个应该在主席树前学,认真写的
「OI之路」02数据结构-9-cdq分治
「OI之路」02数据结构-10整体二分
「OI之路」02数据结构-11图分治
「OI之路」02数据结构-12虚树
「OI之路」02数据结构-13左偏树
「OI之路」02数据结构-14析合树,这个我只是很浅了解
「OI之路」02数据结构-15树上问题

数学

这里大概是内容最多的,基本教程还是很全的,学习顺序大致也是对的
「OI之路」03数学-1传统数论
「OI之路」03数学-2定理杂烩
「OI之路」03数学-3抽象代数
「OI之路」03数学-4博弈论
「OI之路」03数学-5模意义数域,其实某种意义上就是从传统数论里面拉出来的,不然太长了
「OI之路」03数学-6线性代数认真写的
「OI之路」03数学-7组合数学
「OI之路」03数学-8反演与容斥认真写的
「OI之路」03数学-9自然数幂和
「OI之路」03数学-10积性函数及其前缀和
「OI之路」03数学-11集合幂级数
「OI之路」03数学-12极限与微积分
「OI之路」03数学-13生成函数认真写的
「OI之路」03数学-14多项式全家桶
「OI之路」03数学-15概率论
「OI之路」03数学-16快乐计数认真写的

图论

「OI之路」04图论-1最短路
「OI之路」04图论-2并查集
「OI之路」04图论-3最近公共祖先
「OI之路」04图论-4无向图
「OI之路」04图论-5有向图
「OI之路」04图论-6差分约束
「OI之路」04图论-7生成树
「OI之路」04图论-8-2-SAT
「OI之路」04图论-9二分图
「OI之路」04图论-10其他

动态规划

「OI之路」05动态规划-1入门
「OI之路」05动态规划-2动态规划进阶

字符串

「OI之路」06字符串-1KMP
「OI之路」06字符串-2回文算法认真写的
「OI之路」06字符串-3ExKMP,没需要可以不学,我学完就再没看过了
「OI之路」06字符串-4字典树
「OI之路」06字符串-5AC自动机
「OI之路」06字符串-6后缀数组
「OI之路」06字符串-7后缀自动机
「OI之路」06字符串-8其他

其他

「OI之路」07其他-1网络流
「OI之路」07其他-2-01分数规划
「OI之路」07其他-3启发式搜索
「OI之路」07其他-4哈夫曼树
「OI之路」07其他-5哈希
「OI之路」07其他-6几何
「OI之路」07其他-7一类线性二分
「OI之路」04图论-8第k优解相关
「OI之路」04图论-9带权二分认真写的

偏向题集:
模拟大合集
贪心

板子库

貌似因为太长,网页上没法高亮

可以一键复制,然后用编辑器(如notepad++、vscode一键折叠,其中notepad++是alt+1,vscode是ctrl+K+ctrl+1)

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
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
//随机数
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rd(ll l,ll r){return l+rng()%(r-l+1);}
//树状数组
struct BIT
{
int bit[N];void clear(int val=0){ mem(bit,val); }
int lowbit(int x){return x&-x;}
void ad(int x,int c){ while(x<N) bit[x]+=c,x+=lowbit(x); }
int ask(int x){ int ret=0;while(x>=1) ret+=bit[x],x-=lowbit(x);return ret; }
void ad(int l,int r,int c){ad(l,c),ad(r+1,-c);}
int ask(int l,int r){return ask(r)-ask(l-1);}
}bit;
//zkw
const int M=1<<18;
struct ZKW
{
int a[M<<1];void clear(){mem(a,0x3f);}
void change(int x,int val){x+=M;a[x]=val;while(x>1) x>>=1,a[x]=min(a[x<<1],a[x<<1|1]);}
int ask(int l,int r)
{
l+=M-1,r+=M+1;int ans=INF;
while((l^r)!=1)
{
if(!(l&1)) chmin(ans,a[l+1]);
if(r&1) chmin(ans,a[r-1]);
l>>=1;r>>=1;
}return ans;
}
}zkw;
//线段树-区间加,区间求和
struct SGT
{
#define lc x<<1
#define rc x<<1|1
#define mid (l+r)/2
#define TOP int x=1,int l=1,int r=N-1
#define LC lc,l,mid
#define RC rc,mid+1,r
ll val[N<<2],lz[N<<2];void clear(){mem(val,0),mem(lz,0);}
#define pushdown if(lz[x]) val[lc]+=lz[x]*(mid-l+1),lz[lc]+=lz[x],val[rc]+=lz[x]*(r-mid),lz[rc]+=lz[x],lz[x]=0;
void ad(int fl,int fr,ll c,TOP)
{
if(l==fl and r==fr){val[x]+=c*(r-l+1),lz[x]+=c;return;} pushdown
if(fr<=mid) ad(fl,fr,c,LC); else if(fl>mid) ad(fl,fr,c,RC);
else ad(fl,mid,c,LC),ad(mid+1,fr,c,RC);val[x]=val[lc]+val[rc];
}
ll ask(int fl,int fr,TOP)
{
if(l==fl and r==fr) return val[x]; pushdown
if(fr<=mid) return ask(fl,fr,LC); if(fl>mid) return ask(fl,fr,RC);
return ask(fl,mid,LC)+ask(mid+1,fr,RC);
}
};
//矩阵快速幂
struct Matrix
{
#define W 2
int a[W+1][W+1];Matrix(){memset(a,0,sizeof a);}
Matrix operator * (Matrix b){Matrix c;fo(k,0,W) fo(i,0,W) fo(j,0,W) add(c.a[i][j],1ll*a[i][k]*b.a[k][j]%MOD);return c;}
Matrix friend operator ^ (Matrix x,ll e){Matrix ans;fo(i,0,W)ans.a[i][i]=1;while(e){if(e^1)ans=ans*x;x=x*x;e>>=1;}return ans;}
};
//几何
namespace Geo
{
//#define db double
//const db eps=1e-7;
const db PI=acos(-1);
db sqr(db x){return x*x;}
struct V//向量
{
db x,y;V(db _x=0,db _y=0){x=_x,y=_y;}
V operator + (V b){return V(x+b.x,y+b.y);}
V operator - (V b){return V(x-b.x,y-b.y);}
V operator - (){return V(-x,-y);}
V operator * (db b){return V(x*b,y*b);}
db operator * (V b){return x*b.y-y*b.x;}
db len(){return sqrt(x*x+y*y);}
V Unit(){return V(x/len(),y/len());}
db cross(V a,V b){return V(a.x-x,a.y-y)*V(b.x-x,b.y-y);}
V rotate(db rad){return (V){x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};}
bool operator == (V oth){return fabs(x-oth.x)+fabs(y-oth.y)<=eps;}
}; typedef V pt;
typedef pair<pt,db> cir;
typedef pair<pt,pt> line;
line cir_jd(cir a,cir b)//圆的交点
{
V oo=b.FR-a.FR;assert(oo.len()>eps);
db x=(sqr(a.SE)-sqr(b.SE)+sqr(oo.len()))/oo.len()/2;
pt mid=a.FR+oo*(x/oo.len());
V go=oo.Unit().rotate(PI/2)*sqrt(sqr(a.SE)-sqr(x));return {mid-go,mid+go};
}
db sp(V a,V b)//向量夹角
{
if(fabs(a.x)<=eps and fabs(a.y)<=eps) debug("err\n");
if(fabs(b.x)<=eps and fabs(b.y)<=eps) debug("err\n");
db c=atan2(a.y,a.x),d=atan2(b.y,b.x);
return min(fabs(c-d),PI*2-fabs(c-d));
}
V chui_zu(V a,V b)//向量垂足
{
db len=(b-a).len(),dis=fabs(a*b)/len;
return (a-b).rotate(PI/2)*(dis/len)*(a*b>0?1:-1);
}
};
//最大流
namespace MF
{
const int MAX_N=5e3+10,MAX_M=1e5+10;
int hou[MAX_N],cur[MAX_N];
struct Edge{int y,g,c;}e[MAX_M*2];
int ln=0;int oth(int x){return x&1?x+1:x-1;}
void ins(int x,int y,int c)
{
debug("x=%d y=%d c=%d\n",x,y,c);
e[++ln]=(Edge){y,hou[x],c};hou[x]=ln;
e[++ln]=(Edge){x,hou[y],0};hou[y]=ln;
}
int st,ed;queue<int> q;int h[MAX_N];
bool bfs()
{
memcpy(cur,hou,sizeof hou);
memset(h,-1,sizeof h);q.push(st);h[st]=1;
while(q.size())
{
int x=q.front();q.pop();
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(h[y]==-1 and e[k].c) h[y]=h[x]+1,q.push(y);
}
}return h[ed]>0;
}
int dfs(int x,int flow)
{
if(x==ed) return flow;
int now=0;
for(int k=cur[x];k>0;)
{
int y=e[k].y;
if(h[y]==h[x]+1 and e[k].c)
{
int t=dfs(y,min(flow-now,e[k].c));
e[k].c-=t;e[oth(k)].c+=t;now+=t;
}
if(e[k].c==0) cur[x]=e[k].g;
k=e[k].g;if(flow==now) break;
}
if(now==0) h[x]=-1;
return now;
}
};
//费用流
namespace MCF
{
const int MAX_N=2e4,MAX_M=1e5;
int hou[MAX_N];
struct Edge{int y,g,c,w;}e[MAX_M*2];
int ln=0;int oth(int x){return x&1?x+1:x-1;}
void ins(int x,int y,int c,int w=0)
{
e[++ln]=(Edge){y,hou[x],c,w};hou[x]=ln;
e[++ln]=(Edge){x,hou[y],0,-w};hou[y]=ln;
}
int st,ed;queue<int> q;bool v[MAX_N];
int dis[MAX_N],fm[MAX_N],mic[MAX_N];
int ans=0;
bool solve()
{
memset(dis,0x3f,sizeof dis);
memset(v,0,sizeof v);v[st]=1;
q.push(st);dis[st]=0;mic[st]=INF;
while(q.size())
{
int x=q.front();q.pop();
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(dis[y]>dis[x]+e[k].w and e[k].c)
{
dis[y]=dis[x]+e[k].w;
mic[y]=min(mic[x],e[k].c);fm[y]=k;
if(!v[y]) v[y]=1,q.push(y);
}
}
v[x]=0;
}
if(mic[ed]==0 or dis[ed]==INF) return 0;
ans+=dis[ed]*mic[ed];
for(int x=ed;x!=st;x=e[oth(fm[x])].y) e[fm[x]].c-=mic[ed],e[oth(fm[x])].c+=mic[ed];
return 1;
}
};
//并查集
namespace DSU
{
int fa[N];void clear(){ fo(i,0,N-1) fa[i]=i; }
int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}
void merg(int x,int y){fa[findfa(x)]=findfa(y);}
};
//欧拉序LCA+点分+虚树
int log[N];
struct Tr
{
vc<edge> to[N];int n;
int dep[N],siz[N];ll dis[N];int zm(int x,int y){return dep[x]<dep[y]?x:y;}
int dfn[N],dfnid,stb[20][N];
void pre(int x,int fa=0)
{
stb[0][dfn[x]=++dfnid]=x,dep[x]=dep[fa]+1,siz[x]=1;
for(auto z:to[x]) { int y=z.FR;if(y==fa)continue; dis[y]=dis[x]+z.SE,pre(y,x),stb[0][++dfnid]=x,siz[x]+=siz[y]; }
}
void input(){ fo(i,2,n){ int x=qread(),y=qread(),c=qread();to[x].PB({y,c}),to[y].PB({x,c}); } pre(1); }
int getlca(int x,int y){ x=dfn[x],y=dfn[y];if(x>y)swap(x,y);int lg=log[y-x+1];return zm(stb[lg][x],stb[lg][y-bin(lg)+1]); }
ll getdis(int x,int y){ return dis[x]+dis[y]-2*dis[getlca(x,y)]; }
void preST()
{
fo(i,2,dfnid) log[i]=log[i>>1]+1;
fo(j,1,19) fo(i,1,dfnid-bin(j)+1) stb[j][i]=zm(stb[j-1][i],stb[j-1][i+bin(j-1)]);
}
int sta[N];
void build_Vt(vc<int> &a,int fa[])//虚树
{
int top=0,m=sz(a);//sort(all(a),[&](int x,int y){return dfn[x]<dfn[y];});
fo(i,0,m-1)
{
int x=a[i],lst=0;while(top){ int z=sta[top],lca=getlca(z,x);if(lca==z) break;lst=z,top--,fa[z]=sta[top]; }
if(lst){ int lca=getlca(lst,x);if(!top or sta[top]!=lca) sta[++top]=lca,fa[lst]=lca,a.PB(lca); }
sta[++top]=x;
} fo(i,1,top) fa[sta[i]]=sta[i-1];
}
int G;bool ban[N];
void getrt(int SUM,int x,int fa=0)
{
int mx=0;siz[x]=1;
for(auto z:to[x]){ int y=z.FR;if(y!=fa and !ban[y]) getrt(SUM,y,x),siz[x]+=siz[y],chmax(mx,siz[y]); }
if(2*max(mx,SUM-siz[x])<=SUM) G=x;
}
void build_dvt(int SUM,int x,int Fa[])//点分树
{
getrt(SUM,x),x=G,getrt(SUM,x);ban[x]=1;
for(auto z:to[x]){ int y=z.FR;if(!ban[y]) Fa[y]=x,build_dvt(siz[y],y,Fa); }
}
}T[3];
//边分治
namespace EDC
{
struct Edge{ int y,c,g;bool ban; }e[N*2];int hou[N],ln=1;
void ins(int x,int y,int c){ e[++ln]=Edge{y,c,hou[x],0},hou[x]=ln;e[++ln]=Edge{x,c,hou[y],0},hou[y]=ln; }
int n,val[N];//val是点权,本题无用
void build_binary(vc<edge> son[],int& id,int val[],int x=1,int fa=0)
{
int lst=0;for(auto z:son[x])
{
int y=z.FR;if(y==fa) continue;build_binary(son,id,val,y,x);
if(lst==0) ins(x,y,z.SE),lst=x;
else ++id,ins(id,lst,0),ins(id,y,z.SE),lst=id;
}
}
pii G;vc<bool> ban[N];int siz[N],fuk;
void getrt(int SUM,int x,int fa=0)
{
siz[x]=1;for(int k=hou[x];k;k=e[k].g) {
int y=e[k].y;if(y==fa or e[k].ban) continue;
getrt(SUM,y,x),siz[x]+=siz[y];
if( chmin(fuk,max(siz[y],SUM-siz[y])) ) G={x,k};
}//(D-1)/D
}
int leaf[N],MID[40][N];
ll upds[40][N];//到边分树祖先的距离
void dfs(int dep,int x,int fa=0,ll dis=0){ upds[dep][x]=dis;for(int k=hou[x];k;k=e[k].g) if(e[k].y!=fa and !e[k].ban) dfs(dep,e[k].y,x,dis+e[k].c); }
//----------------
int Fa[N];vc<int> son[N];//虚树结构
ll ans=-bin(62),mx[2][N];int col[N],tag[N];
void solve(int dep,ll Midlen,int x,int fa=0)
{
mx[0][x]=mx[1][x]=-bin(61);if(tag[x] and x<=n) mx[col[x]][x]=T[0].dis[x]+upds[dep][x];
for(auto y:son[x]) if(y!=fa)
{
solve(dep,Midlen,y,x);
fo(a,0,1) chmax(ans, mx[a][x]+mx[a^1][y]+Midlen-2*T[1].dis[x] );
fo(a,0,1) chmax(mx[a][x],mx[a][y]);
}
}
//----------------
void eDC(vc<int> &pt,int x,int dep,int l,int r)//边分树,pt不记录辅助点
{
if(l==r) { leaf[l]=x;if(x<=n) pt.PB(x);return; }
fuk=INF;getrt(r-l+1,x);x=G.FR;int y=e[G.SE].y;e[G.SE].ban=e[G.SE^1].ban=1;ll midlen=e[G.SE].c;
dfs(dep,x),dfs(dep,y); MID[dep][l]=l+siz[x]-1;
vc<int> gl,gr;eDC(gl,x,dep+1,l,MID[dep][l]),eDC(gr,y,dep+1,MID[dep][l]+1,r);
int m1=sz(gl),m2=sz(gr),i=0,j=0;pt.resize(m1+m2);
while(i<m1 and j<m2) if(T[1].dfn[gl[i]]<T[1].dfn[gr[j]]) pt[i+j]=gl[i],i++; else pt[i+j]=gr[j],j++;
while(i<m1) pt[i+j]=gl[i],i++;while(j<m2) pt[i+j]=gr[j],j++;
for(auto x:gl) col[x]=0,tag[x]=1;for(auto x:gr) col[x]=1,tag[x]=1;vc<int> VV=pt;T[1].build_Vt(VV,Fa);
for(auto x:VV) son[x].clear();int rt;for(auto x:VV) if(Fa[x]) son[Fa[x]].PB(x); else rt=x;solve(dep,midlen,rt);
for(auto x:pt) tag[x]=0;
}
}; using namespace EDC;
//manacher
void manacher(char str[],int ma[])
{
int ln=strlen(str+1);string s2(ln*2+2);
for(int i=1;i<=ln;i++) s2[2*i-1]='#',s2[2*i]=str[i];
ln=ln*2+1;s2[ln]='#';
int md,rx=0;
for(int i=1;i<=ln;i++)
{
ma[i]=(i<=rx?min(ma[2*md-i],rx-i+1):1);
while(i-ma[i]>=1 and i+ma[i]<=ln and s[i-ma[i]]==s[i+ma[i]]) ma[i]++;
if(rx<i+ma[i]-1) rx=i+ma[i]-1,md=i;
}
}
//kmp
int kmp(char str[],int n,char str2[],int m,int nxt[])
{
fo(i,2,n)
{
int j=nxt[i-1];while(j and str[j+1]!=str[i]) j=nxt[j];
nxt[i]=j+(str[j+1]==str[i]);
}
int ret=0;
for(int i=1,j=0;i<=m;i++)
{
while(j and str[j+1]!=str2[i]) j=nxt[j];
j+=(str[j+1]==str2[i]);if(j==n) ret++,j=nxt[j];
}return ret;
}
//HASH
char str[N];int n;
namespace HASH
{
ll base[2],mod[2],bs[2][N];
void prehash(){
base[0]=131;mod[0]=998244353;base[1]=13331;mod[1]=993244853;
bs[0][0]=bs[1][0]=1;for(int i=1;i<N;i++) bs[0][i]=bs[0][i-1]*base[0]%mod[0],bs[1][i]=bs[1][i-1]*base[1]%mod[1];
}
pr hash(pr old,int add){return MP((old.FR*base[0]+add)%mod[0],(old.SE*base[1]+add)%mod[1]);}
pr hh[N];void prehh(){fo(i,1,n) HASH::hh[i]=HASH::hash(HASH::hh[i-1],str[i]);}
int mm2(int num,int mo){return num<mo?num:num-mo;}
pr gethh(int l,int r){
return MP(
mm2(hh[r].FR+mod[0]-hh[l-1].FR*bs[0][r-l+1]%mod[0],mod[0]),
mm2(hh[r].SE+mod[1]-hh[l-1].SE*bs[1][r-l+1]%mod[1],mod[1]));
}
};
//SCC
namespace SCC
{
stack<int> sta;bool insta[N];
int dfnid,dfn[N],low[N],blg[N],bid,bsiz[N];
void clear(){mem(dfn,0);mem(bsiz,0);dfnid=bid=0;}
void tarjan(vc<int> to[],int x)
{
insta[x]=1;sta.push(x);dfn[x]=low[x]=++dfnid;
for(auto y:to[x])
if(!dfn[y]) tarjan(y),chmin(low[x],low[y]);
else if(insta[y]) chmin(low[x],dfn[y]);
if(dfn[x]==low[x])
{
bid++;
while(1)
{
int now=sta.top();sta.pop();insta[now]=0;
blg[now]=bid;bsiz[bid]++;if(now==x) break;
}
}
}
};
//左右第一个更大的
void getMX(int a[],int lf[],int rf[],int n,bool eq)//eq=[允许相同]
{
stack<int> sta;a[0]=a[n+1]=INF;
fo(i,0,n){ while(sz(sta) and (a[sta.top()]<a[i] or (a[sta.top()]==a[i] and !eq)))sta.pop();lf[i]=(sz(sta)?sta.top():0),sta.push(i); }
while(sz(sta)) sta.pop();
fd(i,n+1,1){ while(sz(sta) and (a[sta.top()]<a[i] or (a[sta.top()]==a[i] and !eq)))sta.pop();rf[i]=(sz(sta)?sta.top():0),sta.push(i); }
}
//min_25筛
namespace min25
{
const int UB=1e6+10;
ll f(ll p,ll k){return p^k;}
bool nop[UB];ll prn,prm[UB];ll S1[UB],S[UB];
void init()
{
fo(i,2,UB-1)
{
if(!nop[i]) prm[++prn]=i,S1[prn]=mm(S1[prn-1]+i),S[prn]=mm(S[prn-1]+f(i,1));
for(int j=1;j<=prn and i*prm[j]<UB;j++)
{
int t=i*prm[j];nop[t]=1;
if(i%prm[j]==0) break;
}
}
}
ll M;ll g[2][UB<<1],h[UB<<1];vc<ll> nn;
#define id(x) ((x)<=UB?(x):UB+M/(x))
ll solve(ll _M)
{
M=_M;mem(g,0),mem(h,0);nn.clear();for(ll l=1;l<=M;l++) nn.PB(M/l),l=M/(M/l);//降序
for(auto n:nn) g[0][id(n)]=n%MOD,g[1][id(n)]=n%MOD*(n%MOD+1)%MOD*((MOD+1)/2)%MOD;
fo(j,1,prn) for(auto n:nn) { if(n<prm[j]*prm[j])break;
add(g[0][id(n)],MOD-mm( g[0][id(n/prm[j])]+MOD-(j-1)-1 ) );
add(g[1][id(n)],MOD-( g[1][id(n/prm[j])]+MOD-S1[j-1]-1 )*prm[j]%MOD );
}
for(auto n:nn) h[id(n)]=(g[1][id(n)]+MOD-g[0][id(n)]+(n>=2)*2)%MOD;
fd(j,prn,1) for(auto n:nn) { if(n<prm[j]*prm[j])break;
for(ll z=1,pp=prm[j],lf=n/pp;lf>0;z++,pp=pp*prm[j],lf/=prm[j])//避免爆ll
add(h[id(n)], ( (lf/prm[j]>0?h[id(n/pp)]+MOD-S[j]:0)+(z>1) )*f(prm[j],z)%MOD );
}
return mm(h[id(M)]+1);
}
};
//FWT
namespace FWT
{
void LN(vc<ll> &z,int n)
{
vc<ll> w(n+1);w[0]=z[1];assert(z[0]==1);
fo(i,1,n-1){ w[i]=z[i+1]*(i+1)%MOD;fo(j,1,i) add(w[i],MOD-z[j]*w[i-j]%MOD); }
z[0]=0;fo(i,1,n) z[i]=w[i-1]*Inv[i]%MOD;
}
void EXP(vc<ll> &z,int n)
{
vc<ll> w(n+1);w[0]=1;assert(z[0]==0);
fo(i,0,n-1){ fo(j,0,i) add(w[i+1],w[j]*z[i-j+1]%MOD*(i-j+1)%MOD);w[i+1]=w[i+1]*Inv[i+1]%MOD; }
z=w;
}
void kPOW(vc<ll> &z,int n,int k)
{
int pos=0;while(pos<=n and !z[pos]) pos++;if(pos*k>n or pos>n){ fo(i,0,n) z[i]=0;return; }//debug k=0
int val=z[pos],iv=invm(val);vc<ll> w(n-pos+1);fo(i,0,n-pos) w[i]=z[pos+i]*iv%MOD;
LN(w,n-pos);fo(i,0,n-pos) w[i]=w[i]*k%MOD;EXP(w,n-pos);
val=qpower(val,k);fo(i,0,n) z[i]=0;fo(i,0,n-pos) if(pos*k+i<=n) z[pos*k+i]=val*w[i]%MOD;
}
void kEXP(vc<ll> &z,int n,int k)
{
vc<ll> w(n+1);for(ll now=1,i=0;i<=k;i++,now=now*z[0]%MOD) add(w[0],now*facinv[i]%MOD);
vc<ll> c(n+1);c=z;kPOW(c,n,k);fo(i,0,n) c[i]=c[i]*facinv[k]%MOD;
fo(i,0,n-1){ fo(j,0,i) add(w[i+1],(w[j]+MOD-c[j])*z[i-j+1]%MOD*(i-j+1)%MOD);w[i+1]=w[i+1]*Inv[i+1]%MOD; }
z=w;
}
void fmt(ll f[],int n,int op=0){ fo(i,0,n-1) fo(s,0,bin(n)-1) if(s&bin(i)) op?add(f[s],MOD-f[s^bin(i)]):add(f[s],f[s^bin(i)]); }
const int B=21;ll h[B+1][bin(B)];
void solve(ll g[],ll f[],int n,int k)//change here
{
fo(ln,0,n) {fo(s,0,bin(n)-1) h[ln][s]=(ln==PC(s)?g[s]:0);fmt(h[ln],n);}
fo(s,0,bin(n)-1){
vc<ll> z(n+1);fo(ln,0,n) z[ln]=h[ln][s];
kEXP(z,n,k);//change here
fo(ln,0,n) h[ln][s]=z[ln];
} fo(ln,0,n) fmt(h[ln],n,1);fo(s,0,bin(n)-1) f[s]=h[PC(s)][s];
}
};
//线性基
namespace BS
{
ll bs[100];int cnt,zero;void clear(){mem(bs,0);cnt=zero=0;}
void insert(ll num)
{
fd(i,60,0) if(num&bin(i))
{
if(!bs[i]) {
fo(t,0,i-1) if(num&bin(t)) num^=bs[t];
fo(t,i+1,60) if(bs[t]&bin(i)) bs[t]^=num;
bs[i]=num,cnt++;return;
}
else num^=bs[i];
}zero++;
}
ll findkth(ll k){ll ret=0,right=cnt;k-=(zero>0);fd(i,60,0)if(bs[i]){right--;if(k&bin(right))ret^=bs[i],k-=bin(right);}return k?-1:ret;}
ll findrk(ll num){ll rk=0,right=cnt;fd(i,60,0)if(bs[i]){right--;if(num&bin(i))rk|=bin(right);}return rk;}
};
//线性筛
bool nop[N];int prn,prm[N],mu[N];
void pre()
{
mu[1]=1;
fo(i,2,N-1)
{
if(!nop[i]) prm[++prn]=i,mu[i]=-1;
for(int j=1;j<=prn and prm[j]*i<N;j++)
{
int t=prm[j]*i;nop[t]=1;mu[t]=-mu[i];
if(i%prm[j]==0){ mu[t]=0;break; }
}
}
}
namespace PP//全家桶板子
{
const int LN=1<<19;int inv[LN+1];
struct NTT
{
vc<int> w[30];NTT(){inv[1]=1;for(int i=2;i<=LN;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
for(int i=1;i<=20;i++) {w[i].resize(bin(i));w[i][0]=1;int pp=qpower(3,(MOD-1)/bin(i));for(int j=1;j<bin(i-1);j++) w[i][j]=1ll*w[i][j-1]*pp%MOD;}
}
int R[LN];inline void DFT(int A[],int lg,int op=0)
{
int m=bin(lg);assert(m<=LN);if(op) reverse(A+1,A+m);
for(int i=1;i<m;i++){R[i]=(R[i>>1]>>1)|((i&1)<<(lg-1));if(R[i]<i)swap(A[i],A[R[i]]);}
for(int ln=1,lgg=1;ln<m;ln<<=1,lgg++) for(int st=0;st<m;st+=2*ln) for(int k=0;k<ln;k++)
{int t=1ll*w[lgg][k]*A[st+ln+k]%MOD;A[st+ln+k]=mm(A[st+k]+MOD-t);A[st+k]=mm(A[st+k]+t);}
}
}ntt;
int _A[LN],_B[LN],_C[LN],M;
struct P//此结构体内函数选择性写
{
vc<int> a;int n;void rs(int nn){a.resize(n=nn);}P(){rs(M);}
int& operator [] (int x){return a[x];}
friend const P operator * (P a,const int &b) {for(int i=0;i<a.n;i++) a[i]=(ll)a[i]*b%MOD;return a;}
inline void dft(int _A[],int lg,int ln){for(int i=0;i<bin(lg);i++)_A[i]=(i<min(ln,n)?a[i]:0);ntt.DFT(_A,lg);}
inline void idft(int _A[],int lg,int ln){ntt.DFT(_A,lg,1);rs(ln);for(int i=0;i<ln;i++)a[i]=1ll*_A[i]*inv[bin(lg)]%MOD;}
const P Mul(P b,int ln=M)
{
int lg=ceil(log2(ln+ln-1)),m=bin(lg);dft(_A,lg,ln);b.dft(_B,lg,ln);
for(int i=0;i<m;i++) _B[i]=1ll*_A[i]*_B[i]%MOD;b.idft(_B,lg,ln);return b;
}
const P operator * (const P b) {return Mul(b);}
};
void Inv(P &a,P &b,int ln=M)
{
if(ln==1){b.rs(1);b[0]=invm(a[0]);return;}Inv(a,b,(ln+1)/2);
int lg=ceil(log2(ln+ln-1)),m=bin(lg);a.dft(_A,lg,ln);b.dft(_B,lg,ln);
for(int i=0;i<m;i++) _B[i]=(2+MOD-1ll*_B[i]*_A[i]%MOD)*_B[i]%MOD;b.idft(_B,lg,ln);
}
P Ji(P a){a.rs(a.n+1);for(int i=a.n-1;i>=1;i--)a[i]=1ll*a[i-1]*inv[i]%MOD;a[0]=0;return a;}
P Dao(P a){for(int i=0;i<a.n-1;i++)a[i]=1ll*a[i+1]*(i+1)%MOD;a.rs(a.n-1);return a;}
P Ln(P &a,int ln=M){P b;Inv(a,b,ln);return Ji(Dao(a).Mul(b,ln-1));}
void Exp(P &a,P &b,int ln=M)
{
if(ln==1){b.rs(1);b[0]=1;return;}Exp(a,b,(ln+1)/2);
P pp=Ln(b,ln);for(int i=0;i<ln;i++) pp[i]=mm(a[i]+MOD-pp[i]);pp[0]++;
int lg=ceil(log2(ln+ln-1)),m=bin(lg);pp.dft(_A,lg,ln);b.dft(_B,lg,ln);
for(int i=0;i<m;i++) _B[i]=1ll*_A[i]*_B[i]%MOD;b.idft(_B,lg,ln);
}
void Sqrt(P &a,P &b,int ln=M)
{
if(ln==1){b.rs(1);b[0]=1;return;}Sqrt(a,b,(ln+1)/2);P tmp=b*2,c;Inv(tmp,c,ln);
int lg=ceil(log2(ln+ln-1)),m=bin(lg);a.dft(_A,lg,ln);b.dft(_B,lg,ln);c.dft(_C,lg,ln);
for(int i=0;i<m;i++) _A[i]=ll((ll)_B[i]*_B[i]+_A[i])%MOD*_C[i]%MOD;b.idft(_A,lg,ln);
}
P Rev(P a){reverse(a.a.begin(),a.a.end());return a;}
P Inv(P a,int ln=M){P b;Inv(a,b,ln);return b;}
P Div(const P &a,const P &b){return Rev(Rev(a).Mul( Inv(Rev(b),a.n-b.n+1),a.n-b.n+1 ) );}
P Mul2(P a,P b){M=a.n+b.n-1;return a*b;}
P DandC(vc<P> &A,int l,int r)
{
if(l==r) return A[l];
int mid=(l+r)/2;
return Mul2(DandC(A,l,mid),DandC(A,mid+1,r));
}
};
//计算几何
namespace Geo
{
const db PI=acos(-1);
db sqr(db x){return x*x;}
struct V//向量
{
db x,y;V(db _x=0,db _y=0){x=_x,y=_y;}
V operator + (V b){return V(x+b.x,y+b.y);}
V operator - (V b){return V(x-b.x,y-b.y);}
V operator - (){return V(-x,-y);}
V operator * (db b){return V(x*b,y*b);}
db operator * (V b){return x*b.y-y*b.x;}
db len(){return sqrt(x*x+y*y);}
V Unit(){return V(x/len(),y/len());}
db cross(V a,V b){return V(a.x-x,a.y-y)*V(b.x-x,b.y-y);}
V rotate(db rad){return (V){x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};}
bool operator == (V oth){return fabs(x-oth.x)+fabs(y-oth.y)<=eps;}
}; typedef V pt;
typedef pair<pt,db> cir;
typedef pair<pt,pt> line;
line cir_jd(cir a,cir b)//圆的交点
{
V oo=b.FR-a.FR;assert(oo.len()>eps);
db x=(sqr(a.SE)-sqr(b.SE)+sqr(oo.len()))/oo.len()/2;
pt mid=a.FR+oo*(x/oo.len());
V go=oo.Unit().rotate(PI/2)*sqrt(sqr(a.SE)-sqr(x));return {mid-go,mid+go};
}
db sp(V a,V b)//向量夹角
{
if(fabs(a.x)<=eps and fabs(a.y)<=eps) debug("err\n");
if(fabs(b.x)<=eps and fabs(b.y)<=eps) debug("err\n");
db c=atan2(a.y,a.x),d=atan2(b.y,b.x);
return min(fabs(c-d),PI*2-fabs(c-d));
}
V chui_zu(V a,V b)//向量垂足
{
db len=(b-a).len(),dis=fabs(a*b)/len;
return (a-b).rotate(PI/2)*(dis/len)*(a*b>0?1:-1);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/d645486d.html
转载请注明出处,谢谢!