模板库-数学和计算几何
数学
ntt
常用素数：
P = 1004535809 ====> pr = 3
P = 998244353 =====> pr = 3
\(n\) 存的是项数而不是次数
inline int init(int n){
int max=1;while(max<=n) max<<=1;
for(int i=0;i>1]>>1,rev[i]|=(i&1)?(max>>1):0;
return max;
}
inline void ntt(int n,long long *a,int type){
for(int i=0;i fwt
inline void Or(int n,long long *f){for(int h=1;hlu div
inline void luDiv(int n,ModInt (*l)[N],ModInt (*u)[N],ModInt (*a)[N]){
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
u[i][j]=a[i][j];
for(int k=1;k计算几何
lib
struct Vector{
double x,y;
inline double len(){return std::sqrt(x*x+y*y);}
inline void operator += (const Vector &a){x+=a.x;y+=a.y;}
inline void operator -= (const Vector &a){x-=a.x;y-=a.y;}
inline void operator *= (const double &a){x*=a;y*=a;}
inline void operator /= (const double &a){x/=a;y/=a;}
inline Vector operator + (const Vector &a)const{return {x+a.x,y+a.y};}
inline Vector operator - (const Vector &a)const{return {x-a.x,y-a.y};}
inline Vector operator * (const double &a)const{return {x*a,y*a};}
inline Vector operator / (const double &a)const{return {x/a,y/a};}
inline double operator * (const Vector &a)const{return x*a.x+y*a.y;}
inline double operator ^ (const Vector &a)const{return x*a.y-y*a.x;}
};
struct Line{
Vector p,way;
double ang;
inline void makeLine(const Vector &a,const Vector &b){p=a;way=b;ang=atan2(b.y,b.x);}
};
inline int onRight(const Line &a,const Vector &b){return (a.way^(b-a.p))<=-eps;}
inline Vector intersect(const Line &a,const Line &b){
double x=(b.way^(a.p-b.p))/(a.way^b.way);
return a.p+a.way*x;
}
inline double polygonArea(int n,Vector *a){
double S=0;
for(int i=1;i二维凸包
inline int graham(int n,Vector *p,Vector *stack){
for(int i=2;i<=n;i++) p[i].ang=atan2(p[i].y-p[1].y,p[i].x-p[1].x);
std::sort(p+2,p+1+n);
stack[1]=p[1];int top=1;
for(int i=2;i<=n;i++){
while(top>1&&cross(p[i]-stack[top],stack[top]-stack[top-1])<=eps) top--;
stack[++top]=p[i];
}
stack[++top]=p[1];
return top;
}
半平面交
int left,right;
Line que[N];
inline int halfPlane(int n,Line *a,Vector *p){
std::sort(a+1,a+1+n,cmp);
left=right=0;que[0]=a[1];
for(int i=2;i<=n;i++){
while(left旋转卡壳
inline int nex(int i){return i==n?1:(i+1);}
int main(){
if(n<=3) return printf("%lld\n",(q[2]-q[1]).len()),0;
long long ans=0;
for(int i=1,j=3;i字符串
kmp
manacher
AC 自动机
struct Node{
Node *tr[26],*fail;
int cnt,in;
}dizhi[N],*root=&dizhi[0],*which[N];
int tot;
inline void insert(char *s,int id){
Node *tree=root;
for(int num,i=1;s[i];i++){
num=s[i]-'a';
if(!tree->tr[num]) tree->tr[num]=&dizhi[++tot];
tree=tree->tr[num];
}
which[id]=tree;
}
int left,right;
Node *que[N];
inline void build(){
left=0;right=-1;
root->fail=root;
for(int i=0;i<26;i++){
if(root->tr[i]) root->tr[i]->fail=root,que[++right]=root->tr[i];
else root->tr[i]=root;
}
Node *u;
while(left<=right){
u=que[left++];
for(int i=0;i<26;i++){
if(u->tr[i]){
u->tr[i]->fail=u->fail->tr[i];
que[++right]=u->tr[i];u->fail->tr[i]->in++;
}
else u->tr[i]=u->fail->tr[i];
}
}
}
SAM
struct Node{
Node *son[26];
int len,cnt;
Node *link;
}dizhi[N*2],*root=&dizhi[0],*last=root;
int tot;
inline void add(int c){
Node *p=last,*now=&dizhi[++tot];
now->len=p->len+1;now->cnt=1;
for(;p&&!p->son[c];p=p->link) p->son[c]=now;
if(!p) now->link=root;
else{
Node *q=p->son[c];
if(q->len==p->len+1) now->link=q;
else{
Node *clone=&dizhi[++tot];*clone=*q;
clone->len=p->len+1;clone->cnt=0;
q->link=now->link=clone;
for(;p&&p->son[c]==q;p=p->link) p->son[c]=clone;
}
}
last=now;
}
PAM
struct Node{
Node *son[26],*fail;
int len,cnt;
}dizhi[N],*root0=&dizhi[0],*root1=&dizhi[1],*last;
int tot;
inline void init(){
last=root1;
root0->fail=root1;root1->fail=root0;
root1->len=-1;
tot=1;
}
char s[N];
inline int cnt(Node *u){
if(u==root0||u==root1) return 0;
if(u->cnt) return u->cnt;
return u->cnt=1+cnt(u->fail);
}
inline int insert(int i){
while(s[i-last->len-1]^s[i]) last=last->fail;
if(!last->son[s[i]-'a']){
Node *u=&dizhi[++tot];
u->len=last->len+2;
reg Node *j=last->fail;
while(s[i-j->len-1]^s[i]) j=j->fail;
u->fail=j->son[s[i]-'a'];
if(!u->fail) u->fail=root0;
last->son[s[i]-'a']=u;
}
last=last->son[s[i]-'a'];
return cnt(last);
}