专栏文章

模板代码

yyi_hr
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio19myq
此快照首次捕获于
2025/12/02 11:43
3 个月前
此快照最后确认于
2025/12/02 11:43
3 个月前
查看原文

模板整理

一. 数据结构

1.序列

ST 表

CPP
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]);
}

树状数组

CPP
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;
}

字典树

CPP
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];
}

线段树

CPP
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

离线二维数点

CPP
#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;
}

平衡树

CPP

笛卡尔树

CPP

可持久化线段树

CPP

动态开点线段树

CPP

可分裂/合并线段树

CPP

莫队

CPP
#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;
}

可持久化字典树

CPP

树套树

CPP

颜色段均摊/珂朵莉树

CPP

2.树形结构

点分治

CPP

树链剖分

CPP
#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

CPP
#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.数论

线性筛素数

CPP
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;
		}
	}
}

逆元

CPP
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;

中国剩余定理

CPP
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;

欧拉函数

CPP
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;
		}
	}
}

卢卡斯定理

CPP

原根

CPP

BSGS

CPP
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

CPP

类欧几里得算法

CPP
#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

CPP
#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

CPP
#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

CPP
#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;
}

子集卷积

CPP
#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 卷积

CPP

3.线性代数

矩阵乘法

CPP

矩阵快速幂

CPP

行列式求值

CPP

矩阵树

CPP

4.其他

快速幂

CPP
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;
}

高精度

CPP

FFT 高精乘

CPP
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];
	}
}

复数类

CPP

康托展开

CPP

三. 图论

1.图

存图

有边权
CPP
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;
}
无边权
CPP
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;
}

拓扑排序

CPP
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
CPP
#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
CPP
#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
CPP
#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
CPP

负环

CPP
#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;
}

最小生成树

CPP
#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;
}

强连通分量

CPP
#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;
}

边双连通分量

CPP
#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;
}

点双连通分量

CPP
#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;
}

割点

CPP

欧拉路径

CPP
#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;
}

二分图最大匹配

CPP

差分约束

CPP
#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

CPP
#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;
}

最大流

CPP
#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;
}

费用流

CPP
#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

倍增
CPP
#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;
}
树剖
CPP
#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
CPP

杂项

KMP

CPP
#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;
}

离散化

CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...