前言

本篇文章收录那些一般不会考裸题,但是常用于算法优化等处的算法们。

预计会有以下几种板块:

  1. 数学
  2. 字符串
  3. 其他

一、数学

1. 快速幂

快速幂

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

2. 矩阵快速幂

矩阵快速幂

struct mat{
	int a[N][N];
}a;

mat matmul(mat x,mat y){
	mat cur;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cur.a[i][j]=0;
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			if(x.a[i][k]==0) continue;
			for(int j=0;j<n;j++){
				if(y.a[k][j]==0) continue;
				cur.a[i][j]=(cur.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
			}
		}
	}
	return cur;
}

void matpow(int x){
	mat cur;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			cur.a[i][j]=0;
		cur.a[i][i]=1;
	}
	/*
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			cout<<a.a[i][j]<<" ";
		cout<<"\n";
	}
	*/
//	int cnt=0;
	while(x){
		if(x&1) cur=matmul(cur,a);
		a=matmul(a,a);
//		cnt++;
		x>>=1;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			cout<<cur.a[i][j]<<" ";	
		cout<<"\n";
	}
}

3. 单值求逆元

详情请见数论专题博客

费马小定理:(适用于模数为质数)

//求 n 在 mod p 意义下的逆元
int qpow(int x,int y,int p){}//见快速幂模板

int main(){
	cin>>n>>p;
	cout<<qpow(n,p-2,p);
	return 0;
}

欧拉定理:(适用于两个数互质)

//求 n 在 mod p 意义下的逆元
int qpow(int x,int y,int p){}//见快速幂模板

void varphi_all(){//求 1~n 的所有数的欧拉函数
	vis[1]=true;
	for(int i=2;i<=n;i++){
		if(vis[i]==false){
			phi[i]=i-1;
			prime.push_back(i);
		}
		for(int j=0;j<prime.size();j++){
			int v=prime[j];
			if(i*v>n) break;
			vis[i*v]=true;
			phi[i*v]=phi[i]*phi[v];
			if(i%v==0){
				phi[i*v]=phi[i]*v;
				break;
			}
		}
	}
}

int varphi_one(int x){//只求 x 的欧拉函数
	int cur=n;
	for(int i=2;i*i<=n;i++){
		if(x%i==0){
			cur-=cur/i;
			while(x%i==0) x/=i;
		}
	}
	if(x>1) cur-=cur/x;
	return cur;
}

int main(){
	cin>>n>>p;
	cout<<qpow(n,varphi_one(n)-1,p);
	return 0;
}

扩展欧拉定理:(适用于普遍情况)

扩展欧拉定理

//还要开个 long long
inline int varphi(int x){}//见求单个的欧拉函数模板

inline int qpow(int x,int y,int p){}//见快速幂模板

signed main(){
	ios::sync_with_stdio(false);
	string s;
	cin>>a>>n>>s;
	int m=varphi(n);
	bool f=false;
	for(int i=0;i<s.size();i++){
		int x=s[i]-'0';
		b=b*10+x;
		if(b>=m){
			b=b%m;
			f=true;
		}
	}
	if(f==true) b+=m;
	cout<<qpow(a,b,n);
	return 0;
}

4. 扩展欧几里得算法

扩展欧几里得算法

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

inline void solve(){
	int a,b,c,x,y;
	cin>>a>>b>>c;
	int gcd=exgcd(a,b,x,y);
	if(c%gcd!=0){
		cout<<"-1\n";
		return;
	}
	a/=gcd,b/=gcd,c/=gcd,x*=c,y*=c;
	int tmp;
	if(x<=0){
		tmp=abs(x)/b;
		x=x%b+b,y-=(tmp+1)*a;
		if(y<=0){
			y=y%a+a;
			cout<<x<<" "<<y<<"\n";
			return;
		}
	}
	if(y<=0){
		tmp=abs(y)/a;
		x-=(tmp+1)*b,y=y%a+a;
		if(x<=0){
			x=x%b+b;
			cout<<x<<" "<<y<<"\n";
			return;
		}
	}
	int minx=x,maxx=x,miny=y,maxy=y;
	tmp=x/b;
	minx%=b;
	if(minx==0){
		minx+=b;
		tmp--;
	}
	maxy+=tmp*a;
	tmp=y/a;
	miny%=a;
	if(miny==0){
		miny+=a;
		tmp--;
	}
	maxx+=tmp*b;
	cout<<((maxy-miny)/a)+1<<" "<<minx<<" "<<miny<<" "<<maxx<<" "<<maxy<<"\n";
}

5. 逆元的性质

线性求逆元

乘法逆元

inv[1]=1;
for(int i=1;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p;

阶乘逆元

乘法逆元2

inv[n+1]=qpow(ti[n],p-2,p);
for(int i=n;i>=1;i--) inv[i]=1ll*inv[i+1]*a[i]%p;

预处理组合数

for(int i=0;i<=n;i++) C[i][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;

二、字符串

详情请见字符串专题

1. Trie

Trie

int n,m;
int nex[N][30],cnt;
//nex表示下一个孩子的编号
//cnt是已经存储的编号
bool vis[N],las[N];
//vis是针对与这道题目的,表示以前是否访问过
//las表示该节点是不是单词的末尾

void update(string &s){//&代表只读取这个字符串,但不更改
	int now=0;
	for(int i=0;i<s.size();i++){
		int tmp=s[i]-'a';
		if(nex[now][tmp]==0) nex[now][tmp]=++cnt;//如果以前没访问过就要增点
		now=nex[now][tmp];//访问它的儿子
	}
	las[now]=true;//这个节点就是单词末尾
}

int query(string &s){
//return 0:存在这个单词,并且以前没有访问过
//return 1:不存在这个单词
//return 2:存在这个单词,但以前访问过
	int now=0;
	for(int i=0;i<s.size();i++){
		int tmp=s[i]-'a';
		if(nex[now][tmp]==0) return 1;//还没有这个节点,表示根本就没这个单词
		now=nex[now][tmp];
	}
	if(las[now]==false) return 1;//不是单词,但是已出现的单词的一个前缀
	else if(vis[now]==false){
		vis[now]=true;
		return 0;
	}
	return 2;
}

2. KMP

KMP

void kmp(string &s){
	int x=0;
	for(int i=1;i<s.size();i++){
		while(x!=0&&s[x]!=s[i]) x=fail[x-1];
		if(s[x]==s[i]) x++;
		fail[i]=x;
	}
}

void fin(string &s,string &t){
	int x=0;
	for(int i=0;i<s.size();i++){
		while(x!=0&&t[x]!=s[i]) x=fail[x-1];
		if(t[x]==s[i]) x++;
		if(x==t.size()){
			cout<<i-x+2<<"\n";
			x=fail[x-1];
		}
	}
}

3. Manacher

Manacher

void manacher(){
	int mid=0,r=0;
	for(int i=1;i<n;i++){
		if(i<=r)
			d[i]=min(d[mid*2-i],r-i+1);
		else d[i]=1;
		while(s[i+d[i]]==s[i-d[i]]) d[i]++;
		if(i+d[i]-1>r) r=i+d[i]-1,mid=i;
	}
}

三、其他

1. Johnson 全源最短路

Johnson全源最短路

bool spfa(int s){
	queue<int>q;
	memset(h,0x3f,sizeof(h));
	h[s]=0;
	cnt[s]=1;
	vis[s]=true;
	q.push(s);
	while(q.empty()==false){
		int x=q.front();
		q.pop();
		vis[x]=false;
		if(cnt[x]>n) return false;
		for(int i=head[x];i;i=edge[i].nex){
			int v=edge[i].to;
			if(h[v]<=h[x]+edge[i].w) continue;
			h[v]=h[x]+edge[i].w;
			if(vis[v]==true) continue;
			vis[v]=true;
			q.push(v);
			cnt[v]++;
		}
	}
	return true;
}

void dijkstra(int s){
	for(int i=1;i<=n;i++) dis[i]=(int)1e9;
	memset(vis,0,sizeof(vis));
	priority_queue<Node>q;
	dis[s]=0;
	Node sta={s,0};
	q.push(sta);
	while(q.empty()==false){
		int x=q.top().id;
		q.pop();
		if(vis[x]==true) continue;
		vis[x]=true;
		for(int i=head[x];i;i=edge[i].nex){
			int v=edge[i].to;
			if(dis[v]<=dis[x]+edge[i].w) continue;
			dis[v]=dis[x]+edge[i].w;
			Node nex={v,dis[v]};
			q.push(nex);
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	for(int i=1;i<=n;i++) add(0,i,0);
	if(spfa(0)==false){
		cout<<"-1\n";
		return 0;
	}
	for(int i=1;i<=m;i++){
		int x=edge[i].fro,y=edge[i].to;
		edge[i].w+=h[x]-h[y];
	}
	for(int i=1;i<=n;i++){
		dijkstra(i);
		long long sum=0;
		for(int j=1;j<=n;j++){
			if(dis[j]==(int)1e9){
				sum+=(long long)j*(int)1e9;
			}
			else sum+=(long long)j*(long long)(dis[j]+h[j]-h[i]);
		}
		cout<<sum<<"\n";
	}
	return 0;
}

2. 差分约束

差分约束

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int n,m;
int head[N<<1],tot;
int dis[N],cnt[N];
bool f,vis[N];

struct node{
	int nex,to,w;
}edge[N<<1];

void add(int x,int y,int w){
	edge[++tot].to=y;
	edge[tot].nex=head[x];
	edge[tot].w=w;
	head[x]=tot;
}

void spfa(int s){
	queue<int>q;
	for(int i=1;i<=n;i++) dis[i]=INT_MAX;
	dis[s]=0;
	vis[s]=true;
	cnt[s]=1;
	q.push(s);
	while(q.empty()==false){
		int x=q.front();
		q.pop();
		vis[x]=false;
		if(cnt[x]>n) return;
		for(int i=head[x];i;i=edge[i].nex){
			int v=edge[i].to,w=edge[i].w;
			if(dis[v]<=dis[x]+w) continue;
			dis[v]=dis[x]+w;
			if(vis[v]==false){
				vis[v]=true;
				q.push(v);
				cnt[v]++;
			}
		}
	}
	f=true;
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(y,x,z);
	}
	for(int i=1;i<=n;i++) add(0,i,0);
	spfa(0);
	if(f==false) cout<<"NO";
	else for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
	return 0;
}

3. 离散化

for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		lisan[++m]=a[i].x,lisan[++m]=a[i].y;
	}
	sort(lisan+1,lisan+m+1);
	m=unique(lisan+1,lisan+m+1)-lisan-1;
	for(int i=1;i<=n;i++){
		a[i].x=lower_bound(lisan+1,lisan+m+1,a[i].x)-lisan;
		a[i].y=lower_bound(lisan+1,lisan+m+1,a[i].y)-lisan;
	}

原文地址:http://www.cnblogs.com/Arcka/p/16922954.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性