小鱼干的代码模板

C++程序设计

数据结构

算法

基础算法

快速幂

分治

ll mypow(ll x,ll n){
	if(n==0) return 1%M;
	ll tmp=mypow(x,n/2)%M;
	if(n&1) return tmp*tmp%M*x%M;
	else return tmp*tmp%M;
}

倍增

typedef long long ll;
ll myPow(ll a,ll n){
	if(n==0) return 1%M;
	ll ans=1;
	while(n){
		if(n&1){
			ans*=a,ans%=M;
		}
		n>>=1;
		a*=a,a%=M;
	}
	return ans%M;
}

二进制拆分

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int dp[20];
int main(){
	ll b,p,k;
	cin>>b>>p>>k;
	dp[0]=b;
	for(int i=1;i<32;i++){//预处理 dp[i]表示b的i次方
		dp[i]=dp[i-1]*dp[i-1];
		dp[i]%=k;
	}	
	int l=log2(p);
	ll ans=1;
	for(int i=l;i>=0;i--){
		if((p>>i)&1){
			ans*=dp[i]%k;
			ans%=k;
		}
	}
	cout<<b<<"^"<<p<<" mod "<<k<<"="<<ans%k;
	return 0;
}

数值处理算法

排序算法

字符串相关算法

搜索算法

图论算法

动态规划

数学

欧几里得算法

复杂度 O(log(a+b))O(log(a+b))

递归方式

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

迭代更新

int gcd(int a,int b){
    while(b){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}

埃氏筛

复杂度O(nloglogn)O(nloglogn)

void erPrime(int n){//埃氏筛
    v[0]=v[1]=1;//标记0和1为非质数
    for(int i=2;i<=n;i++){
        if(v[i]) continue;
        cout<<i<<" ";//i是质数
        for(int j=i;j<=n/i;j++) v[j*i]=1;//标记质数i的倍数为非质数
    }
}

欧拉筛

复杂度O(n)O(n)

int erla(int n){//欧拉筛
	int cnt=0;//统计质数个数
	v[0]=v[1]=1;//标记0、1为非质数
	for(int i=2;i<=n;i++){//遍历2~n
		if(!v[i]) prime[cnt++]=i;//将质数i存入质数表中
		for(int j=0;j<cnt&&prime[j]*i<=n;j++){
			v[prime[j]*i]=1;//将质数prime[j]与i的成乘积标为非质数
			if(i%prime[j]==0) break;//若prime[j]已是i的质因子则,结束,防止重复筛选
		}
	}
	return cnt;
}

矩阵快速幂

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=105;
const int M=1e9+7;
struct node{
	ll a[N][N]={0};
	int row,col;
};
node I;//单位矩阵

node matrixMins(node a,node b){//矩阵乘法
	node c;//答案矩阵
	c.row=a.row;
	c.col=b.col;
	int n=c.row,p=c.col,m=a.col;
	//计算矩阵乘法
	for(int i=1;i<=n;i++){
		for(int j=1;j<=p;j++){
			for(int k=1;k<=m;k++){
				c.a[i][j]+=a.a[i][k]*b.a[k][j]%M;
				c.a[i][j]%=M;
			}
		}
	}
	return c;
}
node matrixPow(node a,ll k){//矩阵的幂次方
	if(k==0){// 0次方
		return I;//矩阵的0次方是单位矩阵
	}
	node t=matrixPow(a,k/2);//求 a^{n/2} 次方
	if(k&1){//判断k是否是奇数
		return matrixMins(matrixMins(t,t),a);
	}else{//k是偶数
		return matrixMins(t,t);
	}
}