PS:以后把模板就放这里了~qwq 有时间就填坑233

常用定义

#define Re register#define Ms(a,b) memset(a,(b),sizof(a))#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)#define Ee(i,u) for(Re int i=head[u],v;i;i=nxt[i])typedef long long LL;

数学

筛法

线性筛质数

void getpri() {    int tot=0;    for(int i=2;i<=n;i++) {        if(!vis[i]) pri[++tot]=i;        for(int j=1;i*pri[j]<=n&&j<=cnt;j++) {            vis[i*pri[j]]=1;            if(i%pri[j]==0) break;        }    }}

欧拉函数

void getphi() {    //phi[mn]=phi[m]*phi[n] (gcd(m,n)==1)    //phi[p]=p-1    //phi[np]=phi[n]*p    int tot=0;    for(int i=2;i<=n;i++) {        if(!vis[i]) pri[i]=i,phi[i]=i-1;        for(int j=1;j<=tot&&i*pri[j]<=n;j++) {            vis[i*pri[j]]=1;            if(i%pri[j]==0) {                phi[i*pri[j]]=phi[i]*pri[j];                break;            }             phi[i*pri[j]]=phi[i]*(pri[j]-1);        }    }}int getphi(int x) {//phi[i]=i*(1-1/p1)*(1-1/p2)*....    int sqr=sqrt(x),ret=x;    Fo(i,2,sqr) {        if(x%i==0) ret=ret/i*(i-1);        while(x%i==0) x/=i;    }    return ret;}

莫比乌斯函数

void getmu() {    int tot=0;    for(int i=1;i<=n;i++) {        if(!vis[i]) pri[++tot]=i,mu[i]=-1;        for(int j=1;j<=tot&&i*pri[j]<=n;j++) {            vis[i*pri[j]]=1;            if(i%pri[j]==0) break;//mu[i*pri[j]]=0;            mu[i*pri[j]]=-mu[i];        }    }}

分解质因数

void div(int x) {    int sqr=sqrt(x);    Fo(i,2,sqr) {        if(x%i==0) cout<<<" ";        while(x%i==0) x/=i;    }}void div(int x) {    int sqr=sqrt(x);    for(int i=1;i<=tot&&pri[i]<=sqr;i++) {        if(x%pri[i]==0) cout<
     
      <<" ";        while(x%pri[i]==0) x/=pri[i];    }}
     

快速幂

typedef long long LL;LL qpow(LL a,LL b) {//无模数     LL t=1;    while(b) {        if(b&1) t*=a;        a*=a; b>>=1;    }    return t;}LL qpow(LL a,LL b,LL q) {//有模数     LL t=1;    while(b) {        if(b&1) t=t*a%p;        a=a*a%p; b>>=1;    }    return t;}

矩阵乘法&快速幂

struct Matrix{    int da[N][N];    void clear() {Ms(da,0);}    Matrix operator * (const Matrix oth) {        Matrix t;        Fo(i,1,n) Fo(j,1,n) Fo(k,1,n)             t.da[i][j]=da[i][k]*oth.da[k][j];        return t;    }}Matrix Qpow(Matrix a,int b) {//快速幂    Matrix t;    Fo(i,1,n) t.da[i][i]=1;    while(b) {        if(b&1) t=t*a;        a=a*a; b>>=1;    }    return t;}

ST表

一维

void init() {    lg2[1]=0; Fo(i,2,n) lg2[i]=lg2[i-1]+(1<<(lg2[i-1]+1)==i);    Fo(j,1,lg[n]) for(Re int i=1;i<=n;i++) {        int vi=min(n,i+(1<<(j-1)));        mx[i][j]=max(mx[i][j-1],mx[vi][j-1]);    }}void qry(int l,int r) {    int k=lg2[r-l+1];    return max(mx[l][k],mx[r-(1<

二维

void init() {    lg[1]=0; Fo(i,2,300) lg[i]=lg[i-1]+((1<<(lg[i-1]+1))==i);    Fo(i,1,lg[n]) Fo(x,1,n) Fo(y,1,m)         f[x][y][i][0]=max(f[x][y][i-1][0],f[min(n,x+(1<<(i-1)))][y][i-1][0]);    Fo(i,1,lg[m]) Fo(x,1,n) Fo(y,1,m)         f[x][y][0][i]=max(f[x][y][0][i-1],f[x][min(m,y+(1<<(i-1)))][0][i-1]);    Fo(i,1,lg[n]) Fo(j,1,lg[m]) Fo(x,1,n) Fo(y,1,m) {        int vx=min(n,x+(1<<(i-1))),vy=min(m,y+(1<<(j-1)));        f[x][y][i][j]=max(max(f[x][y][i-1][j-1],f[vx][vy][i-1][j-1])            ,max(f[vx][y][i-1][j-1],f[x][vy][i-1][j-1]));    }   }int qry(int x1,int y1,int x2,int y2) {    int k1=lg[x2-x1+1],k2=lg[y2-y1+1];    return max(max(f[x1][y1][k1][k2],f[x2-(1<
    
     <
    

图论

Dijkstra

typedef pair
    
      PII;priority_queue 
     
      
       ,greater
       
         > Q;void Dij() {    while(!Q.empty()) Q.pop(); Ms(inq,0); Ms(dis,0x3f);    Q.push(PII(dis[S]=0,S));    while(!Q.empty()) {        int u=Q.top().second;Q.pop();        if(inq[u]) continue; inq[u]=1;        Ee(i,u) if(dis[(v=to[i])]>dis[u]+cst[i])             Q.push(PII(dis[v]=dis[u]+cst[i],v));    }}
       
      
     
    

字符串

KMP

void KMP(char *s) {    int len=strlen(s+1),now=0; Ms(nxt,0);    Fo(i,2,len) {        while(now&&s[now+1]!=s[i]) now=nxt[now];        if(s[now+1]==s[i]) now++;        nxt[i]=now;    }}

Manacher

void Manacher(char *s) {    int id=0,mx=0,len=strlen(s+1); Ms(p,0);    Fo(i,1,len) {        p[i]=i>mx?min(p[id*2-i],mx-i):1;        while(i-p[i]>=1&&i+p[i]<=len&&s[i+p[i]]==s[i-p[i]]) p[i]++;        //如果字符串左右两端加上不同字符则不需边界判断        if(i+p[i]>mx) mx=i+p[i],id=i;     }}

AC自动机

queue
    
      Q;struct ACM{    int val[N],fal[N],cnt[N][26],cnt;    void clear() {Ms(fal,0),Ms(val,0),Ms(cnt,0),cnt=0;}    void ins(char *s) {        int len=strlen(s+1),now=0;        Fo(i,1,len) {            int v=s[i]-'a';            if(!nd[now][v]) nd[now][v]=++cnt;            now=nd[now][v];        }        val[now]++;    }    void build() {        Fo(i,0,25) if(nd[0][i]) fal[nd[0][i]]=0,Q.push(nd[0][i]);        while(!Q.empty()) {            int u=Q.front(); Q.pop();            Fo(i,0,25) if(!nd[u][i]) nd[u][i]=nd[fal[u]][i];                else fal[nd[u][i]]=nd[fal[u]][i],Q.push(nd[u][i]);        }    }    int qry(char *s) {        int len=strlen(s+1),now=0,res=0;        Fo(i,1,len) {            now=nd[now][s[i]-'a'];            for(Re t=now;t&&val[t];t=fal[t]) res+=val[t];//1        }        return res;    }};
    

网络流

Dinic

bool bfs() {    Ms(dis,0);    int h=0,t=1; que[++h]=S; dis[S]=1;    while(h<=t) {        int u=que[h++];        Ee(i,u) if(!dis[to[i]]&&cst[i]>0)            dis[to[i]]=dis[u]+1,que[++t]=to[i];    }    return dis[T];}int dfs(int u,int flow) {    if(u==T) return flow;    int used=0;    for(register int &i=cur[u],v;i;i=nxt[i])         if(cst[i]>0&&dis[(v=to[i])]==dis[u]+1) {            int tmp=dfs(v,min(flow-used,cst[i]));            cst[i]-=tmp,cst[i^1]+=tmp;            used+=tmp; if(used==flow) return flow;        }    if(!used) dis[u]=-1;    return used;    }int dinic() {    int res=0;    while(bfs()) {        Fo(i,0,T) cur[i]=head[i];        res+=dfs(S,INF);    }    return res;}

ISAP

//By Menteur_Hxy#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define Re register#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)#define Ee(i,u) for(Re int i=head[u],v;i;i=nxt[i])#define add(a,b,c) nxt[++cnt]=head[a],to[cnt]=b,cst[cnt]=c,head[a]=cntusing namespace std;int read() {    int x=0,f=1; char c=getchar();    while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}    while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();    return x*f;}const int N=10010,M=100010,INF=0x3f3f3f3f;int n,m,s,t,cnt=1,ans;int nxt[M<<1],to[M<<1],cst[M<<1],head[N],cur[N];int gap[N],dis[N],que[N],S[N];void bfs() {    gap[1]=1;dis[t]=1;    int he=0,ta=1; que[++he]=t;    while(he<=ta) {        int u=que[he++];        Ee(i,u) if(!dis[(v=to[i])]) {            dis[v]=dis[u]+1;            gap[dis[v]]++;            que[++ta]=v;        }    }}void ISAP() {    bfs();    memcpy(cur,head,sizeof(head));    int u=s,top=0;    while(dis[s]
         
          cst[S[i]]) tmp=cst[S[i]],now=i; Fo(i,0,top-1) cst[S[i]]-=tmp,cst[S[i]^1]+=tmp; ans+=tmp; top=now; u=to[S[top]^1]; continue; } int v,fla=0; for(register int &i=cur[u];i;i=nxt[i]) if(cst[i]&&dis[(v=to[i])]+1==dis[u]) {fla=1;break;} if(fla) {S[top++]=cur[u]; u=v; continue;} int tmp=n+1; Ee(i,u) if(cst[i]&&dis[(v=to[i])]
         
        
       
      
     
    

数据结构

树状数组

#define Lof(i,a,b) for(Re int i=(a),_=(b);i<=_;i+=i&-i)#define Lor(i,a) for(Re int i=(a);i;i-=i&-i)struct BIT{    int da[N];    void clear() {Ms(da,0);}    void Modify(int x,int d) {Lof(i,x,n)da[x]+=d;}    int query(int x) {int t=0;Lor(i,x)t+=da[x];return t;}}T;struct TDBIT{    int da[N][N][N];    void clear() {Ms(da,0);}    void Modify(int p,int x,int y,int d) { Lof(i,x,n) Lof(j,y,m) da[p][i][j]+=d;}    int qry(int p,int x,int y) {int t=0;Lor(i,x) Lor(j,y) t+=da[p][i][j];return t;}    int query(int p,int x1,int y1,int x2,int y2) {return qry(p,x2,y2)+qry(p,x1-1,y1-1)-qry(p,x1-1,y2)-qry(p,x2,y1-1);}}T;

左偏树

int nd[N][2],dis[N],val[N],fa[N];#define ls nd[x][0]#define rs nd[x][1]int merge(int x,int y) {    if(!x||!y) return x+y;    if(val[x]>val[y]||(val[x]==val[y]&&x>y)) swap(x,y);    fa[rs=merge(rs,y)]=x;    if(dis[ls]

主席树

//以区间第k小为例void ins(int o1,int &o2,int l,int r,int d) {    si[o2=++tot]=si[o1]+1;    if(l==r) {ls[o2]=ls[o1];rs[o2]=rs[o1];return ;}    int mid=(l+r)>>1;    if(d<=mid) ins(ls[o1],ls[o2],l,mid,d),rs[o2]=rs[o1];    else ins(rs[o1],rs[o2],mid+1,r,d),ls[o2]=ls[o1];}int qry(int o1,int o2,int l,int r,int k) {    if(l==r) return l;    int mid=(l+r)>>1,tmp=si[ls[o2]]-si[ls[o2]];    if(k<=tmp) return qry(ls[o1],ls[o2],l,mid,k);    else return qry(rs[o1],rs[o2],mid+1,r,k-tmp);}

其他

高精度

(希望没错qwq)

PS:建议复制下来查看~

const int pwer=8,bas=100000000;struct bign {    vector
    
      s;    bign& clean() {while(!s.back()&&s.size()>1)s.pop_back();return *this;}    bign(LL num=0) {*this=num;}    bign(string str) {*this=str;}    bign& operator=(LL num) {        s.clear();        do {            s.push_back(num%bas);            num/=bas;        } while(num>0);        return *this;    }    bign& operator=(const string &str) {        s.clear();         int x,len=(str.length()-1)/pwer+1;        Fo(i,0,len-1) {            int ed=str.length()-i*pwer;            int st=max(0,ed-pwer);            sscanf(str.substr(st,ed-st).c_str(),"%d",&x);//1            s.push_back(x);        }        return (*this).clean();    }    bign operator+(const bign &num) const {        bign c; c.s.clear();        for(Re int i=0,las=0;;i++) {            if(!las&&i>=s.size()&&i>=num.s.size()) break;//2            int x=las;            if(i
     
      =s.size()&&i>=num.s.size()) break;            int x=las+s[i];            if(i
      
        v(s.size()+num.s.size(),0); bign c; c.s.clear();         LL las=0,siz1=s.size(),siz2=num.s.size();        Fo(i,0,siz1-1) Fo(j,0,siz2-1)             v[i+j]+=(LL)s[i]*num.s[j];        for(Re int i=0;;i++) {            if(!las&&i>=v.size()) break;//3            LL x=v[i]+las;//4            c.s.push_back(x%bas);            las=x/bas;        }        return c.clean();    }    bign operator/(const bign &num) const {        bign c=*this,m; int siz=s.size();        Ro(i,0,siz-1) {            m=m*bas+s[i];            c.s[i]=bsearch(num,m);            m-=num*c.s[i];        }        return c.clean();    }    bign operator%(const bign &num) const {        bign c=*this,m; int siz=s.size();        Ro(i,0,siz-1) {            m=m*bas+s[i];            c.s[i]=bsearch(num,m);            m-=num*c.s[i];        }        return m;    }    int bsearch(const bign &num,const bign &m) const {         int L=0,R=bas-1,mid;        while(1) {            mid=(L+R)>>1;            if(num*mid<=m) {if(num*(mid+1)>m)return mid;else L=mid;}            else R=mid;        }    }    bign& operator+=(const bign &num) {*this=*this+num;return *this;}    bign& operator-=(const bign &num) {*this=*this-num;return *this;}    bign& operator*=(const bign &num) {*this=*this*num;return *this;}    bign& operator/=(const bign &num) {*this=*this/num;return *this;}    bign& operator%=(const bign &num) {*this=*this%num;return *this;}    bool operator<(const bign &num) const {        if(s.size()!=num.s.size()) return s.size()
       
        (const bign &num) const {return num<*this;}    bool operator<=(const bign &num) const {return !(num<*this);}    bool operator>=(const bign &num) const {return !(*this
        
         >(istream &in,bign &num) {string s;if((in>>s)) num=s;return in;}ostream& operator<<(ostream &out,const bign &num) {    out<
         
          >a>>b; cout<
          
           <
          
         
        
       
      
     
    

持续更新中...