[模板] 一些模板

jr_zch · 2023-09-29 22:39:57 · 算法·理论

一些常用的算法 \text{or} 数据结构模板

by jr_zch

\text{Store - Wagner}

void wagner(int turn){
    if(turn<=1) return ;
    for(int i=1;i<=n;i++) is[i]=w[i]=0;
    int sum,id,lst;
    for(int i=1;i<=turn;i++){
        lst=id,sum=-1,id=0;
        for(int j=1;j<=n;j++) if(!del[j]&&!is[j]&&w[j]>sum) sum=w[j],id=j;
        is[id]=1; 
        for(int j=1;j<=n;j++) if(!del[j]&&!is[j]) w[j]+=mp[id][j];
    }
    ans=min(ans,sum);
    del[lst]=1;
    for(int i=1;i<=n;i++){
        mp[id][i]+=mp[lst][i];
        mp[i][id]+=mp[i][lst];
    }
    wagner(turn-1);
    return ;
}

\text{PAM}

struct pam{
    int len,tot,lst;
    int s[maxn],l[maxn],fail[maxn],to[maxn][26];
    void init(){
        tot=2,lst=1;
        l[1]=-1,l[2]=0;
        fail[1]=fail[2]=1;
        memset(s,-1,sizeof(s));
        return ;
    }
    int calc(int x){
        while(s[len-l[x]-1]!=s[len]) x=fail[x];
        return x;
    }
    void insert(int p){
        s[++len]=p;
        int pre=calc(lst);
        if(to[pre][p]){
            lst=to[pre][p];
            return ;
        }else lst=to[pre][p]=++tot;
        l[tot]=l[pre]+2;
        if(pre==1) fail[tot]=2;
        else fail[tot]=to[calc(fail[pre])][p];
        return ;
    }
};

异或线性基

struct basis{
    int emp,len;
    int b[66];
    basis(int _len=0){
        emp=len=_len;
        memset(b,0,sizeof(b));
    }
    bool insert(int x){
        if(!emp) return 0;
        for(int i=len;i>=0;i--){
            if(!x) return 0;
            if(x>>i&1ll){
                if(b[i]) x^=b[i];
                else return (--emp)+(b[i]=x);
            }
        }
        return 0;
    }
    int query(){
        int res=0;
        for(int i=len;i>=0;i--) if(res>>i&1ll^1ll) res^=b[i];
        return res;
    }
}f[maxn];

basis merge(basis x,basis y){
    basis res=x;
    for(int i=x.len;i>=0;i--) if(y.b[i]) res.insert(y.b[i]);
    return res;
}

\text{Cipolla}

struct comple{
    int a,b,sqr,mod;
    comple(int _a=0,int _b=0,int _sqr=0,int _mod=1){
        a=_a,b=_b;
        sqr=_sqr,mod=_mod;
    }
    comple operator *(const comple &x) const{
        return (comple){(a*x.a+b*x.b%mod*sqr)%mod,(a*x.b+b*x.a)%mod,sqr,mod};
    }
};

int qpow(int x,int y,int mod){
    int res=1;
    while(y){
        if(y&1ll) res=res*x%mod;
        x=x*x%mod,y>>=1ll;
    }
    return res;
}

int qpow(comple x,int y){
    comple res=comple(1,0,x.sqr,x.mod);
    while(y){
        if(y&1ll) res=res*x;
        x=x*x,y>>=1ll;
    }
    return res.a;
}

int cipolla(int a,int p){
    a=(a%p+p)%p;
    if(!a) return 0;
    if(p==2) return 1;
    if(qpow(a,p-1>>1ll,p)==p-1) return -1;
    int b=rand()%p;
    while(qpow((b*b-a+p)%p,p-1>>1ll,p)!=p-1) b=rand()%p;
    comple now=(comple){b,1,(b*b-a+p)%p,p};
    int ans=qpow(now,p+1>>1ll);
    return min(ans,p-ans);
}

\text{Miller Rabin / Pollard Rho}

const int pri[8]={0,2,325,9375,28178,450775,9780504,1795265022};

inline int f(int x,int c,int mod){
    return (x*x%mod+c)%mod;
}

inline int abs(int x){
    return x<0?-x:x;
}

inline int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}

int qpow(int x,int y,int mod){
    int res=1;
    while(y){
        if(y%2) res=res*x%mod;
        x=x*x%mod,y/=2;
    }
    return res;
}

bool miller(int num){
    if(num<2||(num>2&&num%2==0)) return 0;
    if(num==2||num==3||num==5||num==7||num==11) return 1;
    int now=num-1,t=0;
    while(!(now%2)) now/=2,t++;
    for(int i=1;i<=7;i++){
        int x=pri[i]%num,mul=qpow(x,now,num),j=0;
        if(!x||x==1||x==num-1||mul==1) continue;
        while(j<t){
            if(mul==num-1) break;
            mul=mul*mul%num,j++;
        }
        if(j==t) return 0;
    }
    return 1;
}

void pollard(int num){
    if(miller(num)){
        ans=max(ans,num);
        return ;
    }
    if(!(num%2)){
        ans=max(ans,(int)2);
        pollard(num/2);
        return ;
    }
    int res=0;
    while(1){
        int st=rand()%num,c=rand()%(num-1)+1;
        for(int t=1,mul=1,x=st,y=st;;t*=2,mul=1,x=y){
            for(int i=1;i<=t;i++){
                y=f(y,c,num),mul=mul*abs(x-y)%num;
                if(!mul) break;
                if(i%127==0){
                    int d=gcd(mul,num);
                    if(d>1){
                        pollard(d),pollard(num/d);
                        return ;
                    }
                }
            }
            if(!mul) break;
            int d=gcd(mul,num);
            if(d>1){
                pollard(d),pollard(num/d);
                return ;
            }
        }
    }
    return ;
}

\text{BSGS}

int bsgs(int x,int r,int mod){
    int lim=sqrt(mod);
    mp.clear(),x%=mod,r%=mod;
    if(!x){
        if(r) return -1;
        else return 1;
    }
    int now=1;
    for(int i=0;i<=lim;i++){
        mp.insert(now*r%mod,i);
        if(i<lim) now=now*x%mod;
    }
    for(int i=1,j=now;i<=mod/lim+1;i++,j=j*now%mod) if(mp.count(j)) return i*lim-mp[j];
    return -1;
}

\text{SSP}

bool spfa(){
    for(int i=1;i<=ed;i++) dis[i]=inf,flow[i]=0;
    dis[st]=0,flow[st]=inf,q.push(st);
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=last[u];~i;i=nxt[i]){
            int v=to[i];
            if(dis[v]>dis[u]+c[i]&&w[i]){
                dis[v]=dis[u]+c[i],pre[v]=i^1;
                flow[v]=min(flow[u],w[i]);
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
    return flow[ed];
}

void mcmf(){
    ass+=flow[ed];
    for(int i=ed;i!=st;i=to[pre[i]]){
        w[pre[i]]+=flow[ed];
        w[pre[i]^1]-=flow[ed];
        ans+=c[pre[i]^1]*flow[ed];
    }
    return ;
}

\text{Dinic}

int dinic(int u,int inw){
    if(u==ed||!inw) return inw;
    int outw=0;
    for(int i=cur[u];~i;i=nxt[i]){
        int v=to[i];
        cur[u]=i;
        if(dis[v]==dis[u]+1&&w[i]){
            int val=dinic(v,min(inw-outw,w[i]));
            outw+=val;
            w[i]-=val;
            w[i^1]+=val;
            if(inw==outw) return outw;
        }
    }
    return outw;
}

哈希表

struct hash_table{
    int cnt;
    int a[mod],l[mod],r[mod],nxt[mod];
    vector<int> cl;
    void init(){
        cnt=0,cl.clear();
        memset(a,0,sizeof(a));
        return ;
    }
    void clear(){
        cnt=0;
        for(int i:cl) a[i]=0;
        cl.clear();
        return ;
    }
    inline int get(int x){
        return x%mod;
    }
    void insert(int key,int val){
        int now=get(key);
        for(int i=a[now];i;i=nxt[i]){
            if(l[i]==key){
                r[i]=val;
                return ;
            }
        }
        if(!a[now]) cl.push_back(now);
        l[++cnt]=key,r[cnt]=val,nxt[cnt]=a[now],a[now]=cnt;
        return ;
    }
    int operator [](int key){
        int now=get(key);
        for(int i=a[now];i;i=nxt[i]) if(l[i]==key) return r[i];
        return 0;
    }
    bool count(int key){
        int now=get(key);
        for(int i=a[now];i;i=nxt[i]) if(l[i]==key) return 1;
        return 0;
    }
};

\text{AC} 自动机

int trnode;
int to[maxl][26],fail[maxl],is[maxl];
queue<int> q;

void insert(int id){
    int now=0;
    for(int i=1;i<=l[id];i++){
        int nxt=s[id][i]-'a';
        if(!to[now][nxt]) to[now][nxt]=++trnode;
        now=to[now][nxt];
    }
    is[now]++;
    return ;
}

void build(){
    q.push(0);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<26;i++){
            int v=to[u][i];
            if(v){
                if(!u) fail[v]=0;
                else fail[v]=to[fail[u]][i];
                q.push(v);
            }else to[u][i]=to[fail[u]][i];
        }
    }
    return ;
}

\text{ISAP}

int isap(int u,int inw){
    if(u==ed) return inw;
    int outw=0;
    for(int i=cur[u];i<e[u].size();i++){
        int v=e[u][i];
        cur[u]=i;
        if(dis[u]==dis[v]+1&&mp[u][v]){
            int val=isap(v,min(inw-outw,mp[u][v]));
            outw+=val;
            mp[u][v]-=val;
            mp[v][u]+=val;
            if(dis[st]==ed||inw==outw) return outw;
        }
    }
    c[dis[u]]--;
    if(!c[dis[u]]) dis[st]=ed;
    dis[u]++;
    c[dis[u]]++;
    cur[u]=0;
    return outw;
}

李超线段树——直线

struct line{
    bool p;
    int k,b;
    int gety(int x){
        return p?k*x+b:-inf;
    }
}data[maxn<<5];

void update(int &rt,int l,int r,line val){
    if(!rt) rt=++trnode;
    if(l==r){
        int u=data[rt].gety(l),v=val.gety(l);
        if(v>u) data[rt]=val; 
        return ;
    }
    int mid=l+r>>1ll;
    if(data[rt].p){
        int ul=data[rt].gety(l),ur=data[rt].gety(r);
        int vl=val.gety(l),vr=val.gety(r);
        if(ul>=vl&&ur>=vr) return ;
        if(vl>=ul&&vr>=ur){
            data[rt]=val;
            return ;
        }
        int u=data[rt].gety(mid),v=val.gety(mid);
        if(v>u){
            swap(data[rt],val),swap(u,v);
            swap(ul,vl),swap(ur,vr);
        }
        if(vl>ul) update(ls[rt],l,mid,val);
        else update(rs[rt],mid+1,r,val);
    }else data[rt]=val;
    return ;
}

int query(int rt,int l,int r,int x){
    if(!rt) return -inf;
    if(l==r) return data[rt].gety(x);
    int mid=l+r>>1ll,res=data[rt].gety(x);
    if(x<=mid) return max(res,query(ls[rt],l,mid,x));
    else return max(res,query(rs[rt],mid+1,r,x));
}

\text{KMP}

int find(int lens,int lent,char *s,char *t){
    t[lent+1]='#';
    for(int i=lent+2;i<=lens+lent+1;i++) t[i]=s[i-lent-1];
    for(int i=2;i<=lens+lent+1;i++){
        int now=pre[i-1];
        while(now&&t[i]!=t[now+1]) now=pre[now];
        pre[i]=now+(t[i]==t[now+1]);
    }
    for(int i=lent+2;i<=lens+lent+1;i++) if(pre[i]==lent) return i-lent-1;
    return -1;
}

最小表示法

int get(int lens,int *s){
    int i=1,j=2,k=0;
    while(i<=lens&&j<=lens&&k<lens){
        if(s[i+k]>s[j+k]) i+=k+1,k=0;
        else if(s[i+k]<s[j+k]) j+=k+1,k=0;
        else k++;
        if(i==j) i++;
    }
    return min(i,j);
}

高斯消元

int gauss(int n,int m){
    int i=1,j=1,r;
    while(i<=n&&j<=m){
        r=i;
        for(int k=i+1;k<=n;k++) if(fabs(a[k][j])>fabs(a[r][j])) r=k;
        if(fabs(a[r][j])>eps){
            for(int k=1;k<=m+1;k++) swap(a[i][k],a[r][k]);
            for(int k=i+1;k<=n;k++){
                double val=a[k][j]/a[i][j];
                for(int l=j;l<=m+1;l++) a[k][l]-=a[i][l]*val;
            }
            i++;
        }
        j++;
    }
    for(int k=i;k<=n;k++) if(fabs(a[k][m+1])>0) return -1;
    if(i<=m) return 0;
    for(int i=m;i;i--){
        x[i]=a[i][m+1];
        for(int j=i+1;j<=m;j++) x[i]-=a[i][j]*x[j];
        x[i]/=a[i][i];
    }
    return 1;
}

特殊高斯消元 - 线性异或方程

bitset<maxn> a[maxn];

int gauss(int n,int m){
    int i=1,j=1,r;
    while(i<=n&&j<=m){
        r=i;
        for(int k=i+1;k<=n;k++){
            if(a[r][j]) break;
            if(a[k][j]>a[r][j]) r=k;
        }
        if(a[r][j]){
            if(i!=r) swap(a[i],a[r]);
            for(int k=i+1;k<=n;k++) if(a[k][j]) a[k]^=a[i];
            i++;
        }
        j++;
    }
    for(int k=i;k<=n;k++) if(a[k][m+1]) return 0;
    if(i<=m) return -1;
    for(int i=m;i;i--){
        x[i]=a[i][m+1];
        for(int j=i+1;j<=m;j++) x[i]^=a[i][j]*x[j];
    }
    return 1;
}

\text{ExCRT / ExGCD}

struct node{
    int r,p;
}q[maxn];

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int excrt(node q[],int tot,int limit){
    int res=q[1].r,now=q[1].p;
    for(int i=2,x,y;i<=tot;i++){
        int d=exgcd(now,q[i].p,x,y);
        if((q[i].r-res)%d) return -1;
        x*=(q[i].r-res)/d,x=(x%(q[i].p/d)+q[i].p/d)%(q[i].p/d);
        res+=now*x,now*=q[i].p/d;
        if(res>limit) break;
    }
    for(int i=1;i<=tot;i++) if(res%q[i].p!=q[i].r) return -1;
    return res;
}

\text{ExLucas}

int qpow(int x,int y,int mod){
    if(!y) return 1;
    if(y==1) return x;
    int val=qpow(x,y>>1ll,mod);
    if(y&1ll) return val*val%mod*x%mod;
    else return val*val%mod;
}

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int excrt(){
    int res=q[1].r,now=q[1].m;
    for(int i=2,x,y;i<=idx;i++){
        int d=exgcd(now,q[i].m,x,y);
        if((q[i].r-res)%d) return -1;
        x*=(q[i].r-res)/d,x=(x%(q[i].m/d)+q[i].m/d)%(q[i].m/d);
        res+=now*x,now*=q[i].m/d;
    }
    return res;
}

int get(int val,int mod){
    int sum=0,now=mod;
    while(val/now) sum+=val/now,now*=mod;
    return sum;
}

int calc(int val,int p,int mod){
    if(val<=p) return pfac[val];
    return calc(val/p,p,mod)*qpow(pfac[mod],val/mod,mod)%mod*pfac[val%mod]%mod;
}

void init(int p,int mod){
    pfac[0]=1;
    for(int i=1;i<=mod;i++){
        if(i%p) pfac[i]=pfac[i-1]*i%mod;
        else pfac[i]=pfac[i-1];
    }
    return ;
}

int exlucas(int x,int y,int mod){
    if(x<y) return 0;
    int byx,byy,byz,phi,rmod=mod;
    idx=0;
    for(int i=2;i*i<=mod&&i<=1e6;i++){
        if(!(rmod%i)){
            int now=1;
            while(!(rmod%i)) rmod/=i,now*=i;
            q[++idx]=(node){0,now,i};
        }
    }
    if(rmod>1) q[++idx]=(node){0,rmod,rmod};
    for(int i=1;i<=idx;i++){
        init(q[i].p,q[i].m),phi=q[i].m-q[i].m/q[i].p-1;
        byx=get(x,q[i].p),byy=get(y,q[i].p),byz=get(x-y,q[i].p);
        q[i].r=calc(x,q[i].p,q[i].m)*qpow(calc(y,q[i].p,q[i].m),phi,q[i].m)%q[i].m*qpow(calc(x-y,q[i].p,q[i].m),phi,q[i].m)%q[i].m*qpow(q[i].p,byx-byy-byz,q[i].m)%q[i].m;
    }
    return excrt();
}

\text{Dijkstra}

int dis[maxn];
bool vis[maxn];
struct node{
    int to,len;
    bool operator<(const node &a) const{
        return len>a.len;
    }
};
vector<node> e[maxn];
priority_queue<node> q;

void dijkstra(int st){
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    q.push((node){st,0});
    while(!q.empty()){
        int u=q.top().to;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=0;i<e[u].size();i++){
            int v=e[u][i].to; 
            if(dis[v]>dis[u]+e[u][i].len){
                dis[v]=dis[u]+e[u][i].len;
                q.push((node){v,dis[v]});
            }
        }
    }
    return ;
}

\text{SPFA}

void spfa(){
    for(int i=1;i<=n;i++) dis[i]=inf;
    q.push(st),dis[st]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=last[u];~i;i=nxt[i]){
            int v=to[i];
            if(dis[v]>dis[u]+w[i]){
                dis[v]=dis[u]+w[i];
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
    return ;
}

矩阵

struct matrix{
    int row,col;
    int mp[maxn][maxn]={};
    matrix(int _row=0,int _col=0){
        row=_row,col=_col;
    }
    matrix operator+(const matrix &b) const{
        matrix c=matrix(row,col);
        for(int i=1;i<=row;i++){
            for(int j=1;j<=col;j++) c.mp[i][j]=mp[i][j]+b.mp[i][j];
        }
        return c;
    }
    matrix operator-(const matrix &b) const{
        matrix c=matrix(row,col);
        for(int i=1;i<row;i++){
            for(int j=1;j<=col;j++) c.mp[i][j]=mp[i][j]-b.mp[i][j];
        }
        return c;
    }
    matrix operator*(const matrix &b) const{
        matrix c=matrix(row,b.col);
        for(int i=1;i<=row;i++){
            for(int k=1;k<=col;k++){
                if(!mp[i][k]) continue;
                for(int j=1;j<=b.col;j++) c.mp[i][j]+=mp[i][k]*b.mp[k][j];
            }
        }
        return c;
    }
};

matrix qpow(matrix a,int b){
    matrix c=matrix(a.row,a.col);
    for(int i=1;i<=a.row;i++) c.mp[i][i]=1;
    while(b){
        if(b&1ll) c=c*a;
        a=a*a,b>>=1ll;
    }
    return c;
}

字典树

struct trie{
    int rot,cnt;
    int f[maxn],s[maxn][maxv];
    trie(){
        rot=1,cnt=2;
    }
    void insert(char w[]){
        int len=strlen(w),now=rot;
        for(int i=0;i<len;i++){
            if(!s[now][w[i]-'a']) s[now][w[i]-'a']=++cnt;
            now=s[now][w[i]-'a']; 
        }
        f[now]++;
        return ;
    }
    void delet(char w[]){
        int len=strlen(w),now=rot;
        for(int i=0;i<len;i++){
            if(!s[now][w[i]-'a']) s[now][w[i]-'a']=++cnt;
            now=s[now][w[i]-'a']; 
        }
        f[now]=max(f[now]-1,0);
        return ;
    }
    bool query(char w[]){
        int len=strlen(w),now=rot;
        for(int i=0;i<len;i++){
            if(!s[now][w[i]-'a']) return 0;
            now=s[now][w[i]-'a']; 
        }
        return f[now];
    }
};

\text{Splay}

void link(int u,bool d,int v){
    s[u][d]=v,f[v]=u;
    return ;
}

void pushup(int u){
    siz[u]=1;
    if(s[u][0]) siz[u]+=siz[s[u][0]];
    if(s[u][1]) siz[u]+=siz[s[u][1]];
    return ;
}

void rotation(int now){
    int u=f[now],v=f[u];
    bool d=s[u][0]==now;
    link(u,d^1,s[now][d]),link(now,d,u),link(v,s[v][1]==u,now);
    pushup(u),pushup(now);
    return ;
}

void splay(int now,int top){
    while(f[now]!=top){
        int u=f[now],v=f[u];
        if(v!=top){
            if((s[u][0]==now)==(s[v][0]==u)) rotation(u); 
            else rotation(now); 
        }
        rotation(now);
    }
    if(top==0) root=now;
}

int find(int val){
    int now=root,d;
    while(now){
        if(val==data[now]){
            splay(now,0);
            return now;
        }
        d=val>data[now];
        if(s[now][d]) now=s[now][d];
        else break;
    }
    return -1;
}

int merge(int l,int r){
    if(!l||!r) return l+r;
    while(s[l][1]) l=s[l][1];
    splay(l,0),link(l,1,r),pushup(l);
    return l;
}

void insert(int val){
    int now=root,d;
    while(now){
        d=val>data[now];
        if(s[now][d]) now=s[now][d];
        else break;
    }
    data[++cnt]=val,siz[cnt]=1;
    if(now) link(now,d,cnt),pushup(now);
    splay(cnt,0);
    return ;
}

void delet(int val){
    int now=find(val);
    if(now==-1) return ;
    splay(now,0);
    f[s[now][0]]=f[s[now][1]]=0;
    root=merge(s[now][0],s[now][1]);
    return ;
}

int count(int val){
    int now=root,t=0;
    while(now){
        if(data[now]<val) t+=siz[s[now][0]]+1,now=s[now][1];
        else now=s[now][0];
    }
    return t;
}

int _rank(int val){
    return count(val)+1;
}

int kth(int val){
    int now=root,t;
    while(now){
        t=siz[s[now][0]]+1;
        if(val==t) break;
        if(val>t) val-=t,now=s[now][1];
        else now=s[now][0];
    }
    if(now) splay(now,0);
    return now;
}