模板（未完结）
模板
存放一些学过的模板，未完结。
- 离散化
//方法一：STL
//a[]为被离散化数组
int a[maxn],t[maxn];
for(int i=1;i<=n;i++)a[i]=read(),t[i]=a[i];
sort(t+1,t+n+1);
int m=unique(t+1,t+n+1)-t-1;//注意要-1；
for(int i=1;i<=n;i++)a[i]=lower_bound(t+1,t+m+1,a[i])-t;//而这里，是不需要-1的；另，n不是m
//方法二：数组离散化
int cmp(Node a,Node b){return a.v- 线段树
//pushup
void pu(int now,int l,int r)
{
sum[now]=sum[ls]+sum[rs];
return ;
}
//pushdown
void pd(int now,int l,int r)
{
sum[ls]+=(mid-l+1)*lazy[now];sum[rs]+=(r-mid)*lazy[now];
lazy[ls]+=lazy[now];lazy[rs]+=lazy[now];
lazy[now]=0;
return ;
}
//buildtree
void build(int now,int l,int r)
{
if(l==r){sum[now]=read();return ;}
build(ls,l,mid);
build(rs,mid+1,r);
pu(now,l,r);
return ;
}
//insert
void ins(int now,int l,int r,int L,int R,int v)
{
if(L<=l&&r<=R){sum[now]+=(r-l+1)*v;lazy[now]+=v;return ;}
if(lazy[now])pd(now,l,r);
if(L<=mid)ins(ls,l,mid,L,R,v);
if(R>=mid+1)ins(rs,mid+1,r,L,R,v);
pu(now,l,r);
}
//query
int query(int now,int l,int r,int L,int R)
{
if(L<=l&&r<=R){return sum[now];}
if(lazy[now])pd(now,l,r);
int ret=0;
if(L<=mid)ret+=query(ls,l,mid,L,R);
if(R>=mid+1)ret+=query(rs,mid+1,r,L,R);
return ret;
}
- 可持久化线段树（主席树）
//1.建树
void build(int &now,int l,int r)
{
now=++tot;
if(l==r){return ;}
build(tree[now].l,l,mid);
build(tree[now].r,mid+1,r);
return ;
}
//2.修改
void update(int &now,int pre,int l,int r,int pos)
{
//动态开点+复制整棵树
now=++tot;
tree[now].l=tree[pre].l;
tree[now].r=tree[pre].r;
tree[now].siz=tree[pre].siz+1;
//如果搜到底了，直接修改+返回
if(l==r)return ;
//线段树二分
if(pos<=mid)update(tree[now].l,tree[pre].l,l,mid,pos);
else update(tree[now].r,tree[pre].r,mid+1,r,pos);
return ;
}
//3.查询区间第k小
int query(int pre,int now,int l,int r,int k)
{
if(l==r)return l;
int t=tree[tree[now].l].siz-tree[tree[pre].l].siz;//求出左儿子中存储的数值个数t
if(t>=k)return query(tree[pre].l,tree[now].l,l,mid,k);//若k//4.查询通用模板
int query(int now,int l,int r,int x)//查询
{
if(l==r){return tree[now].v;}
if(x<=mid)return query(tree[now].l,l,mid,x);
else return query(tree[now].r,mid+1,r,x);
}
一些数论相关模板
- 埃氏筛
memset(vis,0,sizeof(vis));
for(int i=2;i<=n;i++)
{
if(vis[i])continue;//若被标记，则说明不是质数。
cout<- 试除法分解质因数
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
p[++cnt]=i;c[cnt]=0;
while(n%i==0)n/=i,c[cnt]++;
}
}
if(n>1) p[++cnt]=n,c[cnt]=1;//注意一下这里，如果这时候 n 还没被除到1，则说明 n 是质数。
- 试除法求约数及约数个数
int f[maxn],cnt=0;//f数组用来存储约数，cnt表示约数个数。
for(int i=1;i*i<=n;i++)
{
if(!(n%i)){f[++cnt]=i;if(i!=n/i)f[++cnt]=n/i;}//如果不是根号n，那就把n/i也存储进去。
}
for(int i=1;i<=m;i++)cout<- 倍数法求多个数的因数
vectorf[maxn];//由于直接开数组空间不够，所以开了动态数组vector
for(int i=1;i<=n;i++)
for(int j=1;j<=n/i;j++)f[i*j].push_back(i);
for(int i=1;i<=n;i++)
for(int j:f[i])cout< - 欧几里得辗转相除法
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
- 试除法求单个数的欧拉函数
int phi(int n)
{
int ans=n;
for(int i=2;i<=n;i==)
{
if(n%i==0)
{
ans=ans/i*(i-1);//欧拉函数计算公式
while(n%i==0)n/=i;//分解质因数
}
}
if(n>1)ans=ans/n*(n-1);//参考分解质因数“代码实现”(n不是质数)
return ans;
- 线性筛求多个数欧拉函数
OIWiki:
int euler_phi(int x)
{
memset(ip,1,sizeof(ip));
int cnt=0;
ip[1]=0;phi[1]=1;
for(int i=2;i<=n;i++)
{
if(ip[i]){p[++cnt]=i;phi[i]=i-1;}
for(int j=1;j<=cnt&&i*p[j]<=n;j++)
{
ip[i*p[j]]=0;
if(i%p[j])phi[i*p[j]]=phi[i]*phi[p[j]];
else {phi[i*p[j]]=phi[i]*p[j];}
}
}
return cnt;
}
算法竞赛进阶指南：
void euler(int n)
{
memset(vis,0,sizeof(vis));
m=0;
for(int i=2;i<=n;i++)
{
if(vis[i]==0){v[i]=i,p[++cnt]=i;phi[i]=i-1;}
//给当前的数 i 乘上一个质因子
for(int j=1;j<=m;j++)
{
//i 有比p[j]更小的质因子，或者超出 n 的范围，停止循环。
if(p[j]>v[i]||p[j]>n/i)break;
//p[j] 是合数 i*p[j] 的最小质因子。
vis[i*p[j]]=p[j];
phi[i*p[j]]=phi[i]*(i%p[j]?p[j]-1:p[j]);
}
}
}
- 扩展欧几里得算法（exgcd）
int exgcd(int a,int b,int &x,int &y)
{
if(b==0){x=1;y=0;return a;}
int d=exgcd(b,a%b,x,y);
int t=x;x=y;y=t-y*(a/b);
return d;
}
- 乘法逆元
exgcd:
void exgcd(int a,int b,int &x,int &y)//注意这里是void而不是int，因为我们最后要求的不是exgcd，而是里面的 x。
{
if(b==0){x=1;y=0;return ;}
exgcd(b,a%b,y,x);//由于要求的直接是 x，就可以在这里直接把x和y swap一下即可。
y-=x*(a/b);
}
费马小定理（快速幂）:
int qpow(int a, int b) {
int ans = 1;
a=(a%p+p)%p;
for (;b;b >>= 1) {
if (b&1)ans=(a*ans)%p;
a=(a*a)%p;
}
return ans;
}
线性求逆元
inv[0]=1;//注意这里一定要加上0的逆元~~我为此有一道题折腾了一个小时……
inv[1]=1;
for(int i=2;i<=n;i++)inv[i]=(p-p/i)*inv[p%i]%p;
- 中国剩余定理（CRT）
int CRT(int k,int *a,int *b)//*a和*b表示上述n数组和a数组
{
int n=1;ans=0;
for(int i=1;i<=k;i++)n*=b[i];
for(int i=1;i<=k;i++)
{
int m=n/b[i];
int x=0,y=0;
exgcd(m,b[i],x,y);//求逆元
ans=(ans+a[i]*m*x%n)%n;
}
return (ans%n+n)%n;
}
- 扩展中国剩余定理（EXCRT）
int EXCRT()
{
int ans=b[1],M=a[1];
for(int i=2;i<=n;i++)
{
int x=0,y=0;
int A=M,B=a[i],C=(b[i]-ans%B+B)%B;
int d=exgcd(A,B,x,y);
x=mul(x,(C/d),(B/d));
ans+=x*M;
if(c%d)return -1;
M*=B/d;ans=(ans+M)%M;
}
return ans;
}
矩阵相关
- 定义
struct mat{
int n;
int v[maxn][maxn];
mat(){memset(v,0,sizeof(v));}
mat(int N,int one=0)
{
n=N;memset(v,0,sizeof(v));
if(one)for(int i=1;i<=n;i++)v[1][i]=1;
}
};
- 矩阵乘法
mat operator*(mat A,mat B)
{
mat C=mat(A.n);
for(int i=1;i<=C.n;i++)
for(int j=1;j<=C.n;j++)
for(int k=1;k<=C.n;k++)
(C.v[i][j]+=A.v[i][k]*B.v[k][j])%=mod;
return C;
}
- 矩阵快速幂
mat pw(mat A,int T)
{
//cout<>=1;
}
return ret;
}
To be continued……