模板代码集合
Lijunzhuo
·
·
个人记录
开头
此为 \texttt{Lijunzhuo} 专用，未经许可，不准转载或抄袭。
另外，还为了夏令营。
---
## 一，数论模板
### 1. $\texttt{gcd}$ 模板：
```cpp
int gcd(int a,int b)
{
while(b^=a^=b^=a%=b);
return a;
}
long long gcd(long long a,long long b)
{
while(b^=a^=b^=a%=b);
return a;
}
```
#### 另加快速乘模板：
```cpp
long long mul(long long a,long long b,long long mod)
{
return (__int128)a*b%mod;
}
```
### 2. 快速幂（KSM）：
```cpp
long long KSMans;
long long KSM(long long a,long long b,long long p)
{
ans=1,a%=p;
while(b)
{
if(b&1)
KSMans=KSMans*a%p;
b>>=1;
a=a*a%p;
}
return KSMans;
}
```
### 3. 矩阵乘法+快速幂：
```cpp
const int N=105,MOD=1e9+7;
long long n,k;
struct Matrix
{
long long M[N][N];
};
Matrix A,ANS;
Matrix Mul(const Matrix& A,const Matrix& B,int a,int b,int c,long long m)
{
Matrix C;
memset(C.M,0,sizeof(C.M));
for(int i=0;i<a;i++)
for(int j=0;j<b;j++)
for(int k=0;k<c;k++)
C.M[i][k]=(C.M[i][k]+A.M[i][j]*B.M[j][k]%m)%m;
return C;
}
Matrix Mul(const Matrix& A,const Matrix& B,int n,long long m)
{
return Mul(A,B,n,n,n,m);
}
Matrix qpow(Matrix n,long long m,long long p,int a)
{
Matrix C;
for(int i=0;i<a;i++)
for(int j=0;j<a;j++)
if(i==j) C.M[i][j]=1;
else C.M[i][j]=0;
while(m)
{
if(m&1)
C=Mul(C,n,a,p);
n=Mul(n,n,a,p);
m>>=1;
}
return C;
}
```
### 4. Exgcd模板：
```cpp
void Exgcd(long long a,long long b,long long &x,long long &y)
{
if(!b) x=1,y=0;
else Exgcd(b,a%b,y,x),y-=a/b*x;
}
```
### 5. 质数筛模板：
#### (1).
```cpp
const int N=100005;
bool vis_prime[N];
int prime[N],tot;
void getprime1(int n)
{
memset(vis_prime,true,sizeof(vis_prime));
tot=0;
vis_prime[0]=vis_prime[1]=false;
for(int i=2;i<=n;i++)
{
if(vis_prime[i])
{
prime[++tot]=i;
for(int j=i;j<=n;j+=i)
vis_prime[j]=false;
}
}
}
void getprime2(long long n)
{
memset(vis_prime,true,sizeof(vis_prime));
tot=0;
vis_prime[0]=vis_prime[1]=false;
for(long long i=2;i*i<=n;i++)
if(vis_prime[i])
for(long long j=i*i;j<=n;j+=i)
vis_prime[j]=false;
for(int i=2;i<=n;i++)
if(vis_prime[i])
prime[++tot]=i;
}
```
#### (2).
```cpp
const int N=100005;
int prime[N],tot;
bitset<N>is_prime;
void getprime3(int n)
{
is_prime.set();
is_prime.reset(0),is_prime.reset(1);
for(int i=2;i<=n;i++)
if(is_prime.test(i))
{
prime[++tot]=i;
for(int j=i*2;j<N;j+=i)
is_prime.reset(j);
}
}
void getprime4(long long n)
{
is_prime.set();
is_prime.reset(0),is_prime.reset(1);
for(long long i=2;i*i<=n;i++)
if(is_prime.test(i))
for(long long j=i*i;j<N;j+=i)
is_prime.reset(j);
for(int i=2;i<=n;i++)
if(is_prime.test(i))
prime[++tot]=i;
}
```
#### (3).
```cpp
const int N=100005;
bool vis_prime[N];
int prime[N],tot;
void GetPrime(int n)
{
memset(vis_prime,true,sizeof(vis_prime));
tot=0;
vis_prime[0]=vis_prime[1]=false;
for(int i=2;i<=n;i++)
{
if(vis_prime[i])
prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<=n;j++)
{
vis_prime[i*prime[j]]=false;
if(i%prime[j]==0)
break;
}
}
}
```
### 6. 筛φ：
#### (1).
```cpp
const int N=100005;
int phi[N];
void Getphi(int n)
{
for(int i=1;i<=n;i++)
phi[i]=i;
for(int i=2;i<=n;i++)
if(phi[i]==i)
for(int j=i;j<=n;j+=i)
phi[j]=phi[j]/i*(i-1);
}
```
#### (2).
```cpp
const int N=100005;
bool is_prime[N];
int phi[N],prime[N],tot;
void Getphi(int n)
{
memset(is_prime,true,sizeof(is_prime));
is_prime[0]=is_prime[1]=false;
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(is_prime[i])
{
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&prime[j]*i<=n;j++)
{
is_prime[i*prime[j]]=false;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}else
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
```
### 7.Lucas
```cpp
//lucas(n,m,p)=cm(n%p,m%p)*lucas(n/p,m/p,p)
//lucas(x,0,p)=1,cm(a,b)=(a!/(a-b)!)^(p-2)mod p
long long ans,p;
long long A[1000005];
long long KSM(long long a,long long b,long long p)
{
ans=1;
while(b)
{
if(b&1)
ans=ans*a%p;
b>>=1;
a=a*a%p;
}
return ans;
}
long long C(long long n,long long m)
{
if(m>n) return 0;
return (A[n]*KSM(A[m],p-2,p)%p*KSM(A[n-m],p-2,p)%p);
}
long long cm(long long a,long long b)
{
return KSM(C(b,a),p-2,p);
}
long long lucas(long long n,long long m,long long p)
{
if(!m) return 1;
return C(n%p,m%p)*lucas(n/p,m/p,p)%p;
}
```
---
## 二，数据结构类模板
### 1. 线段树模板：
```cpp
const int N=100005,M=N<<2;
int n,m,A[N],a,b,c,d;
struct segment_tree
{
long long data,lazy;
}XT[M];
void push_up(int k)
{
XT[k].data=XT[k<<1].data+XT[k<<1|1].data;
}
void change(int l,int r,int k,int a)
{
XT[k].data+=a*(r-l+1);
XT[k].lazy+=a;
}
void push_down(int l,int r,int mid,int k)
{
if(l==r) return ;
change(l,mid,k<<1,XT[k].lazy);
change(mid+1,r,k<<1|1,XT[k].lazy);
XT[k].lazy=0;
}
void build(int l,int r,int k)
{
if(l==r)
{
XT[k].data=A[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,k<<1);
build(mid+1,r,k<<1|1);
push_up(k);
}
void change(int l,int r,int k,int s,int v)
{
if(l==r&&l==s)
{
XT[k].data=v;
return ;
}
int mid=(l+r)>>1;
if(s<=mid)
change(l,mid,k<<1,s,v);
else
change(mid+1,r,k<<1|1,s,v);
push_up(k);
}
long long query(int l,int r,int k,int s,int t)
{
if(l>=s&&r<=t)
return XT[k].data;
int mid=(l+r)>>1;
push_down(l,r,mid,k);
long long res=0;
if(s<=mid)
res+=query(l,mid,k<<1,s,t);
if(t>mid)
res+=query(mid+1,r,k<<1|1,s,t);
return res;
}
void up_date(int l,int r,int k,int s,int t,int a)
{
if(l>=s&&r<=t)
{
change(l,r,k,a);
return ;
}
int mid=(l+r)>>1;
push_down(l,r,mid,k);
if(s<=mid)
up_date(l,mid,k<<1,s,t,a);
if(t>mid)
up_date(mid+1,r,k<<1|1,s,t,a);
push_up(k);
}
```
### 2. 树状数组模板：
```cpp
#define lowbit(x) x&-x
const int N=500005;
int AT[N],n;
void change(int x,int a)
{
for(int i=x;i<=n;i+=lowbit(i))
AT[i]+=a;
}
int query(int x)
{
int res=0;
for(int i=x;i>=1;i-=lowbit(i))
res+=AT[i];
return res;
}
```
### 3. 分块模板
```cpp
const int N=200005,M=1005;
int siz,tot,bel[N],L[M],R[M];
long long A[N],val[M],add[M];
inline void init()
{
siz=sqrt(n);
tot=n/siz+(n%siz>0);
for(int i=1;i<=tot;i++)
L[i]=(i-1)*siz+1,R[i]=min(i*siz,n);
for(int i=1;i<=n;i++)
bel[i]=(i-1)/siz+1;
for(int i=1;i<=n;i++)
val[bel[i]]+=A[i];
}
inline void up_date(int l,int r,long long x)
{
int lb=bel[l],rb=bel[r];
if(lb==rb)
for(int i=l;i<=r;i++)
val[lb]+=x,A[i]+=x;
else
{
for(int i=lb+1;i<=rb-1;i++)
add[i]+=x,val[i]+=x*siz;
for(int i=l;i<=R[lb];i++)
val[lb]+=x,A[i]+=x;
for(int i=L[rb];i<=r;i++)
val[rb]+=x,A[i]+=x;
}
}
inline void up_date(int k,long long x){val[bel[k]]+=x,A[k]+=x;}
inline long long query(int l,int r)
{
int lb=bel[l],rb=bel[r];
long long querysum=0;
if(lb==rb)
for(int i=l;i<=r;i++)
querysum+=A[i]+add[lb];
else
{
for(int i=lb+1;i<=rb-1;i++)
querysum+=val[i];
for(int i=l;i<=R[lb];i++)
querysum+=A[i]+add[lb];
for(int i=L[rb];i<=r;i++)
querysum+=A[i]+add[rb];
}
return querysum;
}
inline long long query(int k){return A[k]+add[bel[k]];}
```
### 4. 平衡树模板
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100005,INF=0x3f3f3f3f;
int n,tot,root,op,x,ans;
struct node
{
int val,rd,l,r,size,cnt;
}T[N];
int create(int val)
{
T[++tot]={val,rand(),0,0,1,1};
return tot;
}
void push_up(int p)
{
T[p].size=T[T[p].l].size+T[T[p].r].size+T[p].cnt;
}
void zig(int &p)//右旋
{
int q=T[p].l;
T[p].l=T[q].r;
T[q].r=p;
p=q;
push_up(T[p].r);
push_up(p);
}
void zag(int &p)//左旋
{
int q=T[p].r;
T[p].r=T[q].l;
T[q].l=p;
p=q;
push_up(T[p].l);
push_up(p);
}
void build()
{
create(-INF);
create(INF);
root=1;
T[1].r=2,
push_up(root);
if(T[2].rd>T[1].rd)
zag(root);
}
void insert(int &p,int x)
{
if(p==0)
p=create(x);
else if(x==T[p].val)
T[p].cnt++;
else if(x<T[p].val)
{
insert(T[p].l,x);
if(T[T[p].l].rd>T[p].rd)
zig(p);
}
else if(x>T[p].val)
{
insert(T[p].r,x);
if(T[T[p].r].rd>T[p].rd)
zag(p);
}
push_up(p);
}
void remove(int &p,int x)
{
if(p==0) return ;
if(x==T[p].val)
{
if(T[p].cnt>1)
T[p].cnt--;
else
{
if(T[p].l||T[p].r)
{
if(!T[p].r||T[T[p].l].rd>T[T[p].r].rd)
{
zig(p);
remove(T[p].r,x);
}else
{
zag(p);
remove(T[p].l,x);
}
}else p=0;
}
}
else if(x<T[p].val)
remove(T[p].l,x);
else if(x>T[p].val)
remove(T[p].r,x);
push_up(p);
}
int getrank(int p,int x)
{
if(!p)
return 1;
if(x==T[p].val)
return T[T[p].l].size+1;
else if(x<T[p].val)
return getrank(T[p].l,x);
else
return T[T[p].l].size+T[p].cnt+getrank(T[p].r,x);
}
int getnum(int p,int rank)
{
if(p==0) return INF;
if(rank<=T[T[p].l].size)
return getnum(T[p].l,rank);
else if(rank<=T[T[p].l].size+T[p].cnt)
return T[p].val;
else
return getnum(T[p].r,rank-T[T[p].l].size-T[p].cnt);
}
int prev(int p,int x)
{
if(p==0)
return -INF;
if(x<=T[p].val)
return prev(T[p].l,x);
else return max(T[p].val,prev(T[p].r,x));
}
int ne(int p,int x)
{
if(p==0)
return INF;
if(x>=T[p].val)
return ne(T[p].r,x);
else return min(T[p].val,ne(T[p].l,x));
}
int main()
{
srand(time(0));
scanf("%d",&n);
build();
while(n--)
{
scanf("%d%d",&op,&x);
if(op==1)
insert(root,x);
else if(op==2)
remove(root,x);
else if(op==3)
printf("%d\n",getrank(root,x)-1);
else if(op==4)
printf("%d\n",getnum(root,x+1));
else if(op==5)
printf("%d\n",prev(root,x));
else printf("%d\n",ne(root,x));
}
return 0;
}
/*
1.右旋 Zag / 左旋 Zig
(1)右旋
Q=a[P].l
a[P].l=a[Q].r
a[Q].r=P
root=Q
(2)左旋
Q=a[P].r
a[P].r=a[Q].l
a[Q].l=P
root=Q
2.插入
(1)按BST的插入方法，将插入元素X作为新的结点插入
(2)如果插入的是某节点p的左子树，则比较插入后其左子树根优先级
是否>p的优先级（堆值），如果>，则右旋
(3)如果插入的是某节点p的右子树，则比较插入后其右子树根优先级
是否>p的优先级（堆值），如果>，则左旋
3.删除
(1)如果要删除的点p是叶子，直接删
(2)如果要删除的点p，没有右子树，或者左子树根的优先级（堆值）>
其右子树根的优先级（堆值），则右旋
(3)其余情况左旋
4.找前驱
值为x的结点的前驱，指的是值小于X的最大值
对于结点p所对应的子树，如果：
(1) x<=a[p].val 说明前驱在左子树上
(2) x>a[p].val 说明a[p].val可能是前驱，但答案也可能在右子树上
取二者的较大值
找后继方法类似
5.求值x对应的排名
对于结点p所对应的子树，如果
(1) x<a[p].val 说明x在左子树上，则直接在左子树继续找
(2) x>a[p].val 说明x在右子树上，则排名=p左子树大小+p结点+右子树
查找的结果
(3) x==a[p].val 说明找到了x，排名再加上x左子树的大小，再加1
6.求排名为rank的数
对于结点p所对应的子树，如果
(1) rank <= a[a[p].l].size 说明答案在左子树上
(2) 如果不满足条件1，但是满足 rank <= a[a[p].l].size+a[p].cnt
说明当前的结点p就是要找到排名为rank的结点
(3) 如果上述条件都不满足，说明答案在右子树上，到右子树上找
排名为rank-a[a[p].l].size-a[p].cnt的数
*/
```
## 三，图、树论模板
### 1 $\texttt{and}$ 2. 最短路 与 K 短路模板
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
struct node
{
int v,z;
bool operator<(const node&b)const
{
return z>b.z;
}
};
struct starnode
{
int v,nowz,sumz;
bool operator<(const starnode&b)const
{
return sumz>b.sumz;
}
};
int n,m,s,t,k,G[N],cnt[N],vis[N];
vector<node>R1[N],R2[N];
void dij(int s)
{
memset(G,0x3f,sizeof(G));
G[s]=0;
priority_queue<node>P;
P.push({s,0});
while(!P.empty())
{
node ph=P.top();
P.pop();
if(vis[ph.v]) continue;
else vis[ph.v]=true;
for(auto v:R2[ph.v])
if(G[v.v]>G[ph.v]+v.z)
G[v.v]=G[ph.v]+v.z,
P.push({v.v,G[v.v]});
}
}
int Astar(int s)
{
priority_queue<starnode>P;
P.push({s,0,G[s]});
while(!P.empty())
{
starnode ph=P.top();
P.pop();
cnt[ph.v]++;
if(cnt[ph.v]==k)
return ph.sumz;
for(auto v:R1[ph.v])
if(cnt[v.v]<k)
P.push({v.v,ph.nowz+v.z,ph.nowz+v.z+G[v.v]});
}
return -1;
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&s,&t,&k);
for(int i=1;i<=m;i++)
{
int u,v,z;
scanf("%d%d%d",&u,&v,&z);
R1[u].push_back({v,z});
R2[v].push_back({u,z});
}
dij(t);
printf("%d\n",Astar(s));
return 0;
}
```
### 3. $\texttt{Tarjan}
int n,m,dfn[N],low[N],si[N],id[N],inst[N],st[N];
int dfncnt,sit,stot;
vector<int>R[N];
void Tarjan(int u)
{
dfn[u]=low[u]=++dfncnt,
st[++stot]=u,inst[u]=1;
for(auto v:R[u])
{
if(!dfn[v])
Tarjan(v),
low[u]=min(low[u],low[v]);
else if(inst[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++sit;
do{
id[st[stot]]=sit;
++si[sit];
inst[st[stot]]=0;
}while(st[stot--]!=u);
}
}
别忘了：
for(int i=1;i<=n;i++)
R[0].push_back(i);
4. LCA
int n,m,s,up[N][M],dep[N];
vector<int>R[N];
void DFS(int fa,int u,int de)
{
dep[u]=de,up[u][0]=fa;
for(int i=1;i<M;i++)
up[u][i]=up[up[u][i-1]][i-1];
for(auto v:R[u])
{
if(v==fa) continue;
DFS(u,v,de+1);
}
}
int lca(int x,int y)
{
if(dep[x]>dep[y])
swap(x,y);
int cha=dep[y]-dep[x];
for(int i=0;i<M;i++)
if(cha>>i&1)
y=up[y][i];
if(x==y) return x;
for(int i=M-1;i>=0;i--)
if(up[x][i]!=up[y][i])
x=up[x][i],
y=up[y][i];
return up[x][0];
}
5. 最大流最小割问题：dinic
int n,m,s,t,used[N],level[N],iter[N];
struct node{int v,z,p;};
vector<node>G[N];
queue<int>Q;
void BFS(int u)
{
memset(level,0,sizeof(level));
Q.push(u),level[u]=1;
while(!Q.empty())
{
int ph=Q.front();
Q.pop();
for(auto te:G[ph])
if(!level[te.v]&&te.z>0)
{
level[te.v]=level[ph]+1;
Q.push(te.v);
}
}
}
int DFS(int u,int t,int f)
{
if(u==t) return f;
for(int &i=iter[u];i<(int)G[u].size();i++)
{
auto &v=G[u][i];
if(level[u]+1==level[v.v]&&v.z>0)
{
int d=DFS(v.v,t,min(f,v.z));
if(d>0)
{
v.z-=d,
G[v.v][v.p].z+=d;
return d;
}
}
}
return 0;
}
int dinic(int s,int t)
{
int ans=0;
for(;;)
{
BFS(s);
if(level[t]==0)
break;
memset(iter,0,sizeof(iter));
while(1)
{
int p=DFS(s,t,INF);
if(!p) break;
else ans+=p;
}
}
return ans;
}
本人太蒟了，打绷了，先挖个坑，立个 \texttt{flag}，有时间在来打。