模板代码

yi_hr · 2025-09-02 16:59:42 · 个人记录

模板整理

一. 数据结构

1.序列

ST 表

constexpr int N=1e6+9;
int n,m;
int a[N],s[N][30];
void build(){
    for(int i=1;i<=n;i++){
        s[i][0]=a[i];
    }
    int t=log(n)/log(2);
    for(int j=1;j<=t;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            s[i][j]=max(s[i][j-1],s[i+(1<<(j-1))][j-1]);
        }
    }
}
inline int query(int l,int r){
    int t=log(r-l+1)/log(2);
    return max(s[l][t],s[r-(1<<t)+1][t]);
}

树状数组

constexpr int N=1e6+9;
int t[N];
inline int lowbit(int x){return x&(-x);}
inline void update(int x,int val){
    for(int i=x;i<=n;i+=lowbit(i)) t[i]+=val;
}
inline int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=t[i];
    return res;
}

字典树

constexpr int N=3e6+9;
int n,q,a[N];
int t[N][70],cnt[N],id;
inline int num(const char &x){
    if(x>='A'&&x<='Z') return x-'A';
    if(x>='a'&&x<='z') return x-'a'+26;
    return x-'0'+52;
}
inline void insert(string &s){
    int p=0;
    for(auto i : s){
        int x=num(i);
        if(!t[p][x]) t[p][x]=++id;
        p=t[p][x];
        cnt[p]++;
    }
}
inline int find(string &s){
    int p=0;
    for(auto i : s){
        int x=num(i);
        if(!t[p][x]) return 0;
        p=t[p][x];
    }
    return cnt[p];
}

线段树

constexpr int N=1e6+9;
int n,m;
ll a[N];
struct tree{
    ll sum,tag;
}t[N<<2];
#define mid ((l+r)>>1)
inline void f(int p,int len,ll k){
    t[p].sum+=k*len;
    t[p].tag+=k;
}
inline void push_up(int p){
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
inline void push_down(int p,int l,int r){
    f(p<<1,mid-l+1,t[p].tag);
    f(p<<1|1,r-mid,t[p].tag);
    t[p].tag=0;
}
void build(int p,int l,int r){
    if(l==r){
        t[p].sum=a[l];
        return ;
    }
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    push_up(p);
}
void update(int p,int l,int r,int li,int ri,ll x){
    if(li<=l&&ri>=r){
        f(p,r-l+1,x);
        return ;
    }
    push_down(p,l,r);
    if(li<=mid){
        update(p<<1,l,mid,li,ri,x);
    }
    if(ri>mid){
        update(p<<1|1,mid+1,r,li,ri,x);
    }
    push_up(p);
}
ll query(int p,int l,int r,int li,int ri){
    if(li<=l&&ri>=r){
        return t[p].sum;
    }
    push_down(p,l,r);
    ll res=0;
    if(li<=mid){
        res+=query(p<<1,l,mid,li,ri);
    }
    if(ri>mid){
        res+=query(p<<1|1,mid+1,r,li,ri);
    }
    push_up(p);
    return res;
}
#undef mid

离线二维数点

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=2e6+9;
int n,m,a[N];
struct node{
    int x,val;
    int id;
};
int t[N];
inline int lowbit(int x){ return x&(-x);}
inline void update(int x){
    for(int i=x;i<N;i+=lowbit(i)){
        t[i]++;
    }
}
inline int query(int x){
    int res=0;
    for(int i=x;i>=1;i-=lowbit(i)){
        res+=t[i];
    }
    return res;
}
int ans[N],opt;
vector<node> b[N]; 
inline void insert(int id,int x,int y,int val){
    b[x].push_back({y,val,id});
}
void count_point(){
    for(int i=1;i<=n;i++){
        update(a[i]);
        for(auto j : b[i]){
            ans[j.id]+=j.val*query(j.x);
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int l,r,x;
    for(int i=1;i<=m;i++){
        cin>>l>>r>>x;
        opt++;
        insert(opt,r,x,1);
        insert(opt,l-1,x,-1);
    }
    count_point();
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}

平衡树

笛卡尔树

可持久化线段树

动态开点线段树

可分裂/合并线段树

莫队

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
int n,m,k,a[N],pos[N];
struct node{
    int l,r,id;
    bool operator <(const node &x)const{
        return (pos[l]^pos[x.l])?(l<x.l):((pos[l]&1)?r<x.r:r>x.r);
    }
}b[N];
ll ans[N],cnt[N];
ll res;
inline void add(int p){
    //
}
inline void del(int p){
    //
}
void solve(){
    for(int i=1,l=1,r=0;i<=m;i++){
        for(;r<b[i].r;r++) add(r+1);
        for(;r>b[i].r;r--) del(r);
        for(;l<b[i].l;l++) del(l);
        for(;l>b[i].l;l--) add(l-1);
        ans[b[i].id]=res;
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]^=a[i-1];
    }
    int block=n/sqrt(m*2/3);
    for(int i=1;i<=n;i++){
        pos[i]=(i-1)/block+1;
    }
    for(int i=1;i<=m;i++){
        cin>>b[i].l>>b[i].r;
        b[i].id=i;
    }
    sort(b+1,b+1+m);
    solve();
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}

可持久化字典树

树套树

颜色段均摊/珂朵莉树

2.树形结构

点分治

树链剖分

#include<bits/stdc++.h>
#define bug puts("I will go to Peking University with tsq")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
struct edge{
    int next,to;
}e[N];
int head[N],cnt;
inline void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int n,m,r,mod,a[N];
// ds
int fa[N],d[N],sz[N],son[N],top[N],dfn[N],idx;
int ri[N];
void dfs1(int u){
    sz[u]=1;d[u]=d[fa[u]]+1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs1(v);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]){
            son[u]=v;
        }
    }
}
void dfs2(int u,int tp){
    dfn[u]=++idx;
    top[u]=tp;
    if(son[u]) dfs2(son[u],tp);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
    ri[u]=idx;
}
void path_update(int u,int v,int val){
    while(top[u]!=top[v]){
        if(d[top[u]]<d[top[v]]) swap(u,v);
        update(1,1,n,dfn[top[u]],dfn[u],val);
        u=fa[top[u]];
    }
    if(d[u]>d[v]) swap(u,v);
    update(1,1,n,dfn[u],dfn[v],val);
}
void tree_update(int u,int val){
    update(1,1,n,dfn[u],ri[u],val);
}
int path_query(int u,int v){
    int res=0;
    while(top[u]!=top[v]){
        if(d[top[u]]<d[top[v]]) swap(u,v);
        res+=query(1,1,n,dfn[top[u]],dfn[u]);
        res%=mod;
        u=fa[top[u]];
    }
    if(d[u]>d[v]) swap(u,v);
    res+=query(1,1,n,dfn[u],dfn[v]);
    res%=mod;
    return res;
}
int tree_query(int u){
    return query(1,1,n,dfn[u],ri[u]);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>r>>mod;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int u,v;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    fa[r]=r;
    dfs1(r);
    dfs2(r,r);
    for(int i=1;i<=n;i++){
        update(1,1,n,dfn[i],dfn[i],a[i]);
    }
    while(m--){
        int op,x,y,z;
        cin>>op;
        if(op==1){
            cin>>x>>y>>z;
            path_update(x,y,z);
        }else if(op==2){
            cin>>x>>y;
            cout<<path_query(x,y)<<'\n';
        }else if(op==3){
            cin>>x>>z;
            tree_update(x,z);
        }else{
            cin>>x;
            cout<<tree_query(x)<<'\n';
        }
    }
    return 0;
}

dsu on tree

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
struct edge{
    int next,to;
}e[N];
int head[N],cnt;
inline void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int n,m,a[N];
int son[N],sz[N];
void dfs1(int u,int fa){
    sz[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]){
            son[u]=v;
        }
    }
}

ll ans[N],opt[N];
ll maxx,sum;
void dfs2(int u,int fa,int p){
    opt[a[u]]++;
    if(opt[a[u]]==maxx){
        sum+=a[u];
    }
    if(opt[a[u]]>maxx){
        sum=a[u];
        maxx=opt[a[u]];
    }
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa||v==p) continue;
        dfs2(v,u,p);
    }
}

void del(int u,int fa){
    opt[a[u]]--;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        del(v,u);
    }
}

void dfs(int u,int fa){
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa||v==son[u]) continue;
        dfs(v,u);
        del(v,u);
        maxx=sum=0;
    }
    if(son[u]){
        dfs(son[u],u);
    }
    dfs2(u,fa,son[u]);
    ans[u]=sum;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int u,v;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs1(1,1);
    dfs(1,1);
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}

二. 数学

1.数论

线性筛素数

int n,p[N];
bitset<N> vis;
void init(){
    int cnt=0;
    for(int i=2;i<=n;i++){
        if(!vis[i]) p[++cnt]=i;
        for(int j=1;j<=cnt&&(i*p[j]<=n);j++){
            vis[i*p[j]]=1;
            if(i%p[j]){
                continue;
            }
            break;
        }
    }
}

逆元

struct INV{
    inline ll qpow(ll x,ll b,ll mod){
        ll res=1;
        for(;b;b>>=1,x*=x,x%=mod){
            if(b&1) res*=x,res%=mod;
        }
        return res;
    }
    inline int inv(int x,int p){
        return qpow(x,p-2,p);
    }
}inv;

中国剩余定理

struct CRT{
    void exgcd(ll a,ll b,ll &x,ll &y){
        if(b==0){
            x=1;
            y=0;
            return ;
        }
        exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
    inline ll inv(ll x,ll p){
        ll a=0,b=0;
        exgcd(x,p,a,b);
        return (a%p+p)%p;
    }
    inline ll crt(int n,ll *a,ll *b){
        ll m=1,x=0;
        for(int i=1;i<=n;i++){
            m*=a[i];
        }
        for(int i=1;i<=n;i++){
            __int128 mi=m/a[i],t=inv(mi,a[i]);
            x+=mi*t*b[i]%m;
            x%=m;
        }
        return x;
    }
}crt;

欧拉函数

int n,p[N],phi[N];
bitset<N> vis;
void init(){
    int cnt=0;
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]) p[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&(i*p[j]<=n);j++){
            vis[i*p[j]]=1;
            if(i%p[j]){
                phi[i*p[j]]=phi[i]*phi[p[j]];
                continue;
            }
            phi[i*p[j]]=phi[i]*p[j];
            break;
        }
    }
}

卢卡斯定理

原根

BSGS

constexpr int N=1e6+9;
inline ll qpow(ll x,ll b,ll mod){
    ll res=1;
    while(b){
        if(b&1){
            res*=x;
            res%=mod;
        }
        x*=x;
        x%=mod;
        b>>=1;
    }
    return res;
}
ll BSGS(ll x,ll y,ll mod){
    x%=mod;
    y%=mod;
    ll m=ceil(sqrt(mod));
    unordered_map<ll,ll> ma;
    ll num=1;
    for(int i=0;i<=m;i++){
        ma[(y*num)%mod]=i;
        num*=x;
        num%=mod;
    }
    num=1;
    ll am=qpow(x,m,mod);
    for(int i=1;i<=m;i++){
        num*=am;
        num%=mod;
        if(ma.find(num)!=ma.end()){
            return i*m-ma[num];
        }
    }
    return -1;
}

exBGSG

类欧几里得算法

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9,mod=998244353;
ll inv2=499122177,inv6=166374059;
struct node{
    node(){f=g=h=0;}
    ll f,g,h;
};
node f(ll a,ll b,ll c,ll n){
    ll m=(a*n+b)/c;
    node d;
    if(a==0){
        d.f=b/c*(n+1)%mod;
        d.g=b/c*n%mod*(n+1)%mod*inv2%mod;
        d.h=b/c*(b/c)%mod*(n+1)%mod;
        return d;
    }
    if(a>=c||b>=c){
        d.f=n*(n+1)%mod*inv2%mod*(a/c)%mod+b/c*(n+1)%mod;
        d.g=a/c*n%mod*(n+1)%mod*(n*2+1)%mod*inv6%mod+b/c*n%mod*(n+1)%mod*inv2%mod;
        d.h=a/c*(a/c)%mod*n%mod*(n+1)%mod*(n*2+1)%mod*inv6%mod+b/c*(b/c)%mod*(n+1)%mod+a/c*(b/c)%mod*n%mod*(n+1)%mod;
        d.f%=mod,d.g%=mod,d.h%=mod;
        node t=f(a%c,b%c,c,n);
        d.h+=t.h+2*(b/c)%mod*t.f%mod+2*(a/c)%mod*t.g%mod;
        d.g+=t.g,d.f+=t.f;
        d.f%=mod,d.g%=mod,d.h%=mod;
        return d;
    }else{
        node t=f(c,c-b-1,a,m-1);
        d.f=n*m%mod-t.f;
        d.f=(d.f%mod+mod)%mod;
        d.g=n*m%mod*(n+1)%mod-t.h-t.f;
        d.g=(d.g*inv2%mod+mod)%mod;
        d.h=n*m%mod*(m+1)%mod-2*t.g-2*t.f-d.f;
        d.h=(d.h%mod+mod)%mod;
        return d;
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        ll n,a,b,c;
        cin>>n>>a>>b>>c;
        node ans=f(a,b,c,n);
        cout<<ans.f<<' '<<ans.h<<' '<<ans.g<<'\n';
    }
    return 0;
}

2.多项式与生成函数

FFT

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr double pi=acos(-1.0);
constexpr int N=5e6+9;
struct cp{
    double a,b;
    cp(double x=0,double y=0){a=x,b=y;}
}a[N],b[N];
cp operator + (const cp &a,const cp &b){ return {a.a+b.a,a.b+b.b};}
cp operator - (const cp &a,const cp &b){ return {a.a-b.a,a.b-b.b};}
cp operator * (const cp &a,const cp &b){ return {a.a*b.a-a.b*b.b,a.a*b.b+a.b*b.a};}
int r[N];
void FFT(int len,cp *a,int t){
    for(int i=0;i<len;i++){
        if(i<r[i]) swap(a[i],a[r[i]]);
    }
    for(int i=1;i<len;i<<=1){
        cp wn={cos(pi/i),t*sin(pi/i)};
        for(int j=0;j<len;j+=(i<<1)){
            cp w={1,0};
            for(int k=0;k<i;k++,w=w*wn){
                cp x=a[j+k],y=w*a[i+j+k];
                a[j+k]=x+y;
                a[i+j+k]=x-y;
            }
        }
    }
}
int n,m,len,l;
void init(){
    len=1,l=0;
    while(len<=n+m) len<<=1,l++;
    for(int i=0;i<len;i++){
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));   
    }
    FFT(len,a,1);
    FFT(len,b,1);
    for(int i=0;i<=len;i++){
        a[i]=a[i]*b[i];
    }
    FFT(len,a,-1);
}
void print(){
    for(int i=0;i<=n+m;i++){
        cout<<(int)(a[i].a/len+0.5)<<" ";
    }
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<=n;i++){
        cin>>a[i].a;
    }
    for(int i=0;i<=m;i++){
        cin>>b[i].a;
    }
    init();
    print();
    return 0;
}

NTT

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=5e6+9,mod=998244353;
inline ll qpow(ll x,ll b,ll mod){
    ll res=1;
    for(;b;b>>=1,x*=x,x%=mod){
        if(b&1) res*=x,res%=mod;
    }
    return res;
}
int r[N],g=3,gi=qpow(3,mod-2,mod);
void NTT(int len,ll *a,int t){
    for(int i=0;i<len;i++){
        if(i<r[i]) swap(a[i],a[r[i]]);
    }
    for(int i=1;i<len;i<<=1){
        ll wn=qpow(t==1?g:gi,(mod-1)/(i<<1),mod);
        for(int j=0;j<len;j+=(i<<1)){
            ll w=1;
            for(int k=0;k<i;k++,w=w*wn%mod){
                int x=a[j+k],y=w*a[i+j+k]%mod;
                a[j+k]=(x+y)%mod;
                a[i+j+k]=(x-y+mod)%mod;
            }
        }
    }
}
int len,l;
ll n,m,a[N],b[N];
void init(){
    len=1,l=0;
    while(len<=n+m) len<<=1,l++;
    for(int i=0;i<len;i++){
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    NTT(len,a,1);
    NTT(len,b,1);
    for(int i=0;i<len;i++){
        a[i]=a[i]*b[i]%mod;
    }
    NTT(len,a,-1);
}
void print(){
    ll inv=qpow(len,mod-2,mod);
    for(int i=0;i<=n+m;i++)
        cout<<(a[i]*inv)%mod<<" ";
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<=n;i++){
        cin>>a[i];
    }
    for(int i=0;i<=m;i++){
        cin>>b[i];
    }
    init();
    print();
    return 0;
}

FWT

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9,mod=998244353;
inline int qpow(ll x,int b){
    ll res=1;
    while(b){
        if(b&1){
            res*=x,res%=mod;
        }
        x*=x,x%=mod;
        b>>=1;
    }
    return res;
}
void FWT_or(int len,ll *a,int t){
    for(int i=2;i<=len;i<<=1){
        int mid=i>>1;
        for(int j=0;j<len;j+=i){
            for(int k=0;k<mid;k++){
                a[j+k+mid]+=a[j+k]*t+mod;
                a[j+k+mid]%=mod;
            }
        }
    }
}
void FWT_and(int len,ll *a,int t){
    for(int i=2;i<=len;i<<=1){
        int mid=i>>1;
        for(int j=0;j<len;j+=i){
            for(int k=0;k<mid;k++){
                a[j+k]+=a[j+k+mid]*t+mod;
                a[j+k]%=mod;
            }
        }
    }
}
void FWT_xor(int len,ll *a,int t){
    for(int i=2;i<=len;i<<=1){
        int mid=i>>1;
        for(int j=0;j<len;j+=i){
            for(int k=0;k<mid;k++){
                ll a1=a[j+k],a2=a[j+k+mid];
                a[j+k]=(a1+a2)*t%mod;
                a[j+k+mid]=(a1-a2+mod)*t%mod;
            }
        }
    }
}
int n,m;
ll a[N],b[N];
ll ai[N],bi[N];
void print(){
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<"\n";
}
void get_or(){
    for(int i=0;i<n;i++) a[i]=ai[i];
    for(int i=0;i<n;i++) b[i]=bi[i];
    FWT_or(n,a,1);
    FWT_or(n,b,1);
    for(int i=0;i<n;i++){
        a[i]=a[i]*b[i]%mod;
    }
    FWT_or(n,a,-1);
    print();
}
void get_and(){
    for(int i=0;i<n;i++) a[i]=ai[i];
    for(int i=0;i<n;i++) b[i]=bi[i];
    FWT_and(n,a,1);
    FWT_and(n,b,1);
    for(int i=0;i<n;i++){
        a[i]=a[i]*b[i]%mod;
    }
    FWT_and(n,a,-1);
    print();
}
void get_xor(){
    for(int i=0;i<n;i++) a[i]=ai[i];
    for(int i=0;i<n;i++) b[i]=bi[i];
    FWT_xor(n,a,1);
    FWT_xor(n,b,1);
    for(int i=0;i<n;i++){
        a[i]=a[i]*b[i]%mod;
    }
    FWT_xor(n,a,qpow(2,mod-2));
    print();
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    n=(1<<n);
    for(int i=0;i<n;i++){
        cin>>ai[i];
    }
    for(int i=0;i<n;i++){
        cin>>bi[i];
    }
    get_or();
    get_and();
    get_xor(); 
    return 0;
}

子集卷积

#include<bits/stdc++.h>
#define ppc __builtin_popcount
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=2e6+9,mod=1e9+9;
void FWT_or(int len,ll *a,int t){
    for(int i=2;i<=len;i<<=1){
        int mid=i>>1;
        for(int j=0;j<len;j+=i){
            for(int k=0;k<mid;k++){
                a[j+k+mid]+=a[j+k]*t+mod;
                a[j+k+mid]%=mod;
            }
        }
    }
}
ll n,m,a[N],b[N];
ll ai[25][N],bi[25][N];
ll ci[45][N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;m=n;
    n=(1<<n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    for(int i=0;i<n;i++){
        ai[ppc(i)][i]=a[i];
        bi[ppc(i)][i]=b[i];
    }

    for(int i=0;i<=m;i++){
        FWT_or(n,ai[i],1);
        FWT_or(n,bi[i],1);
    }
    for(int i=0;i<=m;i++){
        for(int j=0;j<=i;j++){
            for(int k=0;k<n;k++){
                ci[i][k]+=ai[j][k]*bi[i-j][k];
                ci[i][k]%=mod;
            }
        }
    }
    for(int i=0;i<=m;i++){
        FWT_or(n,ci[i],-1);
    }
    for(int i=0;i<n;i++){
        cout<<ci[ppc(i)][i]<<" ";
    }
    return 0;
}

Dirichlet 卷积

3.线性代数

矩阵乘法

矩阵快速幂

行列式求值

矩阵树

4.其他

快速幂

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

高精度

FFT 高精乘

constexpr double pi=acos(-1.0);
constexpr int N=5e6+9;
struct cp{
    double a,b;
    cp(double x=0,double y=0){a=x,b=y;}
}a[N],b[N];
cp operator + (const cp &a,const cp &b){ return {a.a+b.a,a.b+b.b};}
cp operator - (const cp &a,const cp &b){ return {a.a-b.a,a.b-b.b};}
cp operator * (const cp &a,const cp &b){ return {a.a*b.a-a.b*b.b,a.a*b.b+a.b*b.a};}
int r[N];
void FFT(int len,cp *a,int t){
    for(int i=0;i<len;i++){
        if(i<r[i]) swap(a[i],a[r[i]]);
    }
    for(int i=1;i<len;i<<=1){
        cp wn={cos(pi/i),t*sin(pi/i)};
        for(int j=0;j<len;j+=(i<<1)){
            cp w={1,0};
            for(int k=0;k<i;k++,w=w*wn){
                cp x=a[j+k],y=w*a[i+j+k];
                a[j+k]=x+y;
                a[i+j+k]=x-y;
            }
        }
    }
}
int n,m,len,l;
void init(){
    len=1,l=0;
    while(len<=n+m) len<<=1,l++;
    for(int i=0;i<len;i++){
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));   
    }
    FFT(len,a,1);
    FFT(len,b,1);
    for(int i=0;i<=len;i++){
        a[i]=a[i]*b[i];
    }
    FFT(len,a,-1);
}
int ans[N];
void cheng(string &s1,string &s2){
    n=s1.size()-1;
    m=s2.size()-1;
    for(int i=0;i<=n;i++){
        a[i].a=s1[n-i]-'0';
    }
    for(int i=0;i<=m;i++){
        b[i].a=s2[m-i]-'0';
    }
    init();
}
void print(){
    for(int i=0;i<=len;i++){
        ans[i]+=a[i].a/len+0.5;
        if(ans[i]>=10){
            ans[i+1]+=ans[i]/10;
            ans[i]%=10;
        }
    }
    bool flag=1;
    for(int i=len;i>=0;i--){
        if(flag&&ans[i]==0) continue;
        flag=0;
        cout<<ans[i];
    }
}

复数类

康托展开

三. 图论

1.图

存图

有边权

struct edge{
    int next,to,w;
}e[N];
int head[N],cnt;
inline void add(int u,int v,int w){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}

无边权

struct edge{
    int next,to;
}e[N];
int head[N],cnt;
inline void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}

拓扑排序

struct TP{
    int tp[N],idx=0,in[N];
    void tp_sort(){
        queue<int> q;
        for(int i=1;i<=n;i++){
            if(!in[i]){
                q.push(i);
            }
        }
        while(!q.empty()){
            int u=q.front();q.pop();
            tp[++idx]=u;
            for(int i=head[u];i;i=e[i].next){
                int v=e[i].to;
                if(--a[v]==0){
                    q.push(v);
                }
            }
        }
    }
}tp;

单源最短路

SPFA

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
struct edge{
    int next,to,w;
}e[N];
int head[N],cnt;
inline void add(int u,int v,int w){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
int n,m,s,dis[N];
bitset<N> vis; 
void spfa(){
    queue<int> q;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(vis[v]) continue;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                q.push(v);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s;
    int u,v,w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    spfa();
    for(int i=1;i<=n;i++){
        cout<<(dis[i]==INF?((1<<31)-1):dis[i])<<" ";
    }
    return 0;
}

dijkstra

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
struct edge{
    int next,to,w;
}e[N];
int head[N],cnt;
inline void add(int u,int v,int w){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
int n,m,s,dis[N];
struct node{
    int u,dis;
    bool operator <(const node &x)const{
        return dis>x.dis;
    }
};

void dij(){
    priority_queue<node> q;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push({s,0});
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[u]+e[i].w<dis[v]){
                dis[v]=dis[u]+e[i].w;
                q.push({v,dis[v]});
            }
        }   
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s;
    int u,v,w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    dij();
    for(int i=1;i<=n;i++){
        cout<<(dis[i]==INF?((1<<31)-1):dis[i])<<" ";
    }
    return 0;
}

多源最短路

Floyd

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e2+9;
int n,m,a[N][N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=n;i++){
        a[i][i]=0;
    }
    int u,v,w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        a[u][v]=a[v][u]=min(a[u][v],w);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<"\n";
    }   
    return 0;
}

johnson

负环

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e4+9;
struct edge{
    int next,to,w;
}e[N];
int head[N],cnt;
inline void add(int u,int v,int w){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
ll n,m,s,dis[N];
int opt[N];
bitset<N> vis;
void spfa(){
    memset(dis,0x3f,sizeof(dis));
    memset(opt,0,sizeof(opt));
    vis.reset();
    queue<int> q;
    dis[1]=0;
    q.push(1);
    vis[1]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        if(++opt[u]>n+1){
            cout<<"YES\n";
            return ;
        }
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(vis[v]) continue;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                q.push(v);
            }
        }
    }
    cout<<"NO\n";
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        memset(head,0,sizeof(head));
        cnt=0;
        cin>>n>>m;
        int u,v,w;
        for(int i=1;i<=m;i++){
            cin>>u>>v>>w;
            if(w>=0){
                add(u,v,w);
                add(v,u,w);
            }else{
                add(u,v,w);
            }
        }
        spfa();
    }
    return 0;
}

最小生成树

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
int n,m,f[N];
inline int find(int u){
    return (u==f[u]?u:f[u]=find(f[u]));
}
struct node{
    int u,v,w;
    bool operator <(const node &x)const{
        return x.w>w;
    }
}a[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    int u,v,w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        a[i]={u,v,w};
    }
    sort(a+1,a+1+m);
    int ans=0;
    for(int i=1;i<=m;i++){
        int fu=find(a[i].u),fv=find(a[i].v);
        if(fu==fv) continue;
        ans+=a[i].w;
        f[fv]=fu;
    }
    int fo=find(1);
    for(int i=2;i<=n;i++){
        if(find(i)!=fo){
            cout<<"orz";
            return 0;
        }
    }
    cout<<ans;
    return 0;
}

强连通分量

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
struct edge{
    int next,to;
}e[N<<1];
int head[N],cnt;
inline void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int n,m;
int dfn[N],low[N],idx,opt,be[N];
stack<int> s;
bitset<N> ins;
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    ins[u]=1;
    s.push(u);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else{
            if(ins[v]) low[u]=min(low[u],low[v]);
        }
    }
    if(low[u]==dfn[u]){
        ++opt;
        while(1){
            int v=s.top();s.pop();
            ins[v]=0;
            if(v==u) break;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        add(u,v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    //
    return 0;
}

边双连通分量

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
struct edge{
    int next,to;
}e[N<<2];
int head[N],cnt=1;
inline void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int n,m;
int dfn[N],low[N],idx,opt;
bitset<N> ins;
stack<int> s;
void tarjan(int u,int fa){
    dfn[u]=low[u]=++idx;
    ins[u]=1;
    s.push(u);
    for(int i=head[u];i;i=e[i].next){
        if((i>>1)==(fa>>1)) continue;
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
        }else{
            if(ins[v]) low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        ++opt;
        vector<int> p;
        while(1){
            int v=s.top();s.pop();
            ins[v]=0;
            if(v==u)break;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i,-1);
    }
    //
    return 0;
}

点双连通分量

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
struct edge{
    int next,to;
}e[N<<2];
int head[N],cnt=1;
inline void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int n,m;
int dfn[N],low[N],idx,opt;
stack<int> s;
vector<vector<int>> a;
void tarjan(int u,int la){
    dfn[u]=low[u]=++idx;
    s.push(u);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==la) continue;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                ++opt;
                vector<int> p;
                while(1){
                    int x=s.top();s.pop();
                    p.push_back(x);
                    if(x==v) break;
                }
                p.push_back(u);
                a.push_back(p);
            }
        }else{
            low[u]=min(low[u],dfn[v]);
        }
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        if(u==v) continue;
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]&&head[i]) tarjan(i,i);
        if(!dfn[i]&&!head[i]){
            opt++;
            a.push_back(vector<int>{i});
        }
    }
    //
    return 0;
}

割点

欧拉路径

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define ll long long
using namespace std;
const int N=1e5+9;
struct edge{
    int next,to;
}e[N<<2];
int head[N],cnt=1;
inline void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int n,m,a[N];
int now[N],in[N],out[N];
bitset<N<<2> vis;
void sort_edge(){
    vector<int> vec;
    for(int i=1;i<=n;i++){
        vec.clear();
        int op=0;
        now[i]=head[i];
        for(int j=head[i];j;j=e[j].next){
            vec.push_back(e[j].to);
        }
        sort(vec.begin(),vec.end());
        for(int j=head[i];j;j=e[j].next){
            e[j].to=vec[op++];
        }
    }
}
stack<int> s;

void dfs(int u){
    for(int i=now[u];i;i=now[u]){
        now[u]=e[i].next;
        dfs(e[i].to);
    }
    s.push(u);
}

void solve(){
    int cnt_s=0,cnt_t=0,S=1;
    bool flag=1;
    for(int i=1;i<=n;i++){
        if(in[i]!=out[i]){
            flag=0;
            if(in[i]+1==out[i]){
                if(cnt_s){
                    cout<<"No";exit(0);
                }
                cnt_s=1;
                S=i;
            }
            else if(out[i]+1==in[i]){
                if(cnt_t){
                    cout<<"No";exit(0);
                }
                cnt_t=1;
            }else{
                cout<<"No";exit(0);
            }
        }
    }
    if((!flag)&&!(cnt_t==1&&cnt_s==1)){
        cout<<"No";exit(0);
    }
    dfs(S);
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        in[v]++ ;
        out[u]++;
        add(u,v);
    }
    sort_edge();
    solve();
    return 0;
}

二分图最大匹配

差分约束

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
struct edge{
    int next,to,w;
}e[N];
int head[N],cnt;
inline void add(int u,int v,int w){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
int n,m,dis[N],opt[N];
bitset<N> vis;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    int u,v,w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,-w);
    }
    for(int i=1;i<=n;i++){
        add(0,i,0);
    }
//  memset(dis,0x3f,sizeof(dis));
    memset(dis,128,sizeof(dis));
    queue<int> q;
    q.push(0);
    dis[0]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        if(++opt[u]>n){
            cout<<"NO";return 0;
        }
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[u]+e[i].w>dis[v]){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
    return 0;
}
/*
u + w <= v
a - w <= b
*/

2-SAT

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=2e6+9;
struct edge{
    int next,to;
}e[N<<1];
int head[N],cnt;
inline void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int n,m;
int dfn[N],low[N],idx,opt,be[N];
stack<int> s;
bitset<N> ins;
void tarjan(int u){
    dfn[u]=low[u]=++idx;
    ins[u]=1;
    s.push(u);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else{
            if(ins[v]) low[u]=min(low[u],low[v]);
        }
    }
    if(low[u]==dfn[u]){
        ++opt;
        while(1){
            int v=s.top();s.pop();
            ins[v]=0;
            be[v]=opt;
            if(v==u) break;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    int u,v,a,b; 
    for(int i=1;i<=m;i++){
        cin>>u>>a>>v>>b;
        u--;v--;
        u=(u<<1)+(a==1);
        v=(v<<1)+(b==1);
        add(u^1,v);
        add(v^1,u);
    }
    for(int i=0;i<(n<<1);i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int i=0;i<n;i++){
        if(be[i<<1]==be[i<<1|1]){
            cout<<"IMPOSSIBLE";
            return 0;
        }
    }
    cout<<"POSSIBLE\n";
    for(int i=0;i<n;i++){
        if(be[i<<1]>be[i<<1|1]){
            cout<<1<<" ";
        }else{
            cout<<0<<" ";
        }
    }
    return 0;
}

最大流

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f

using namespace std;
constexpr int N=1e5+9;
struct edge{
    int next,to;
    ll w;
}e[N];
int head[N],cnt=1;
inline void add(int u,int v,ll w){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
int n,m,s,t;
ll maxflow;
int d[N],now[N];
bool bfs(){
    memset(d,0,sizeof(d));
    queue<int> q;
    q.push(s);d[s]=1;
    now[s]=head[s];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(e[i].w&&!d[v]){
                q.push(v);d[v]=d[u]+1;
                now[v]=head[v];
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
ll dinic(int u,ll flow){
    if(u==t) return flow;
    ll rest=flow;
    for(int i=now[u];i&&rest;i=e[i].next){
        now[u]=i;
        int v=e[i].to;
        if(e[i].w&&d[u]+1==d[v]){
            ll k=dinic(v,min(e[i].w,rest));
            if(!k)d[v]=0;
            e[i].w-=k;
            e[i^1].w+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s>>t;
    int u,v;
    ll w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    ll flow;
    while(bfs()){
        while(flow=dinic(s,INF)){
            maxflow+=flow;
        }
    }
    cout<<maxflow;
    return 0;
}

费用流

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define ll int
using namespace std;
const int N=5e3+9,M=5e4+9;
struct edge{
    int next,to;
    ll w,c;
}e[M<<1];
int head[N],cnt=1;
inline void add(int u,int v,int w,int c){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].c=c;
    head[u]=cnt;
}
int n,m,s,t,a[N];
int pre[N];
ll dis[N],incf[N];
bitset<N> vis;

bool spfa(){
    queue<int> q;
    memset(dis,0x3f,sizeof(dis));
    vis=0;
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    incf[s]=LINF;
    int u,v;
    while(!q.empty()){
        u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next){
            if(!e[i].w)continue;
            v=e[i].to;
            if(dis[v]>dis[u]+e[i].c){
                dis[v]=dis[u]+e[i].c;
                incf[v]=min(incf[u],e[i].w);
                pre[v]=i;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[t]==INF){
        return 0;
    }else{
        return 1;
    }
}
ll maxflow,mincost;
void update(){
    int x=t;
    while(x!=s){
        int i=pre[x];
        e[i].w-=incf[t];
        e[i^1].w+=incf[t];
        x=e[i^1].to;
    }
    maxflow+=incf[t];
    mincost+=dis[t]*incf[t];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s>>t;
    int u,v,w,c;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w>>c;
        add(u,v,w,c);
        add(v,u,0,-c);
    }
    while(spfa())update();
    cout<<maxflow<<" "<<mincost;
    return 0;
}

2.树

LCA

倍增

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
struct edge{
    int next,to;
}e[N];
int head[N],cnt;
inline void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int n,m,s;
int f[N][30],d[N];
void dfs(int u){
    d[u]=d[f[u][0]]+1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==f[u][0]) continue;
        f[v][0]=u;
        dfs(v);
    }
}
void init(){
    for(int j=1;j<=22;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
}
int lca(int u,int v){
    if(d[u]<d[v]) swap(u,v);
    for(int i=22;i>=0;i--){
        if(d[f[u][i]]>=d[v]){
            u=f[u][i];
        }
    }
    if(u==v) return u;
    for(int i=22;i>=0;i--){
        if(f[u][i]!=f[v][i]){
            u=f[u][i];
            v=f[v][i];
        }
    }
    return f[u][0];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s;
    int u,v;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(s);
    init();
    while(m--){
        cin>>u>>v;
        cout<<lca(u,v)<<"\n";
    }
    return 0;
}

树剖

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
struct edge{
    int next,to;
}e[N];
int head[N],cnt;
inline void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int n,m,s,a[N];
int sz[N],d[N],fa[N],son[N],top[N];
void dfs1(int u){
    sz[u]=1;
    d[u]=d[fa[u]]+1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs1(v);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v]){
            son[u]=v;
        }
    }
}
void dfs2(int u,int tp){
    top[u]=tp;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
    if(son[u]) dfs2(son[u],tp);
}
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(d[top[u]]<d[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(d[u]>d[v]) swap(u,v);
    return u;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s;
    int u,v;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    fa[s]=s;
    dfs1(s);
    dfs2(s,s);
    while(m--){
        cin>>u>>v;
        cout<<lca(u,v)<<"\n";
    }
    return 0;
}

tarjan

杂项

KMP

#include<bits/stdc++.h>
#define debug puts("I will ak ioi")
#define next _yhr_tsq_
#define ll long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
constexpr int N=1e6+9;
int n,m;
string s,t;
int next[N];

void int_next(){
    int j=0;
    next[1]=0;
    for(int i=2;i<=m;i++){
        while(j&&t[j+1]!=t[i]) j=next[j];
        if(t[j+1]==t[i]) ++j;
        next[i]=j;
    }
}
void kmp(){
    int j=0;
    for(int i=1;i<=n;i++){
        while(j&&t[j+1]!=s[i]) j=next[j];
        if(t[j+1]==s[i]) ++j;
        if(j==m){
            cout<<i-m+1<<"\n";
            j=next[j];
        }
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>s>>t;
    n=s.size();m=t.size();
    s=" "+s;t=" "+t;
    int_next();
    kmp();
    return 0;
}

离散化

for(int i=1;i<=n;i++){
    b[i]=a[i];
}
int m=n;
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++){
    a[i]=lower_bound(b+1,b+1+m,a[i])-b;
}