倍增算法C++

倍增

倍增算法是一种优化算法，通常用于某些需要高效计算指数幂的场景。它基于分治的思想，通过反复求平方来实现快速计算指数幂的目的。在实际应用中，倍增算法经常用于解决最近公共祖先问题、二分查找等。

1、快速幂详解

ksm核心代码

倍增就是基于二进制的指数倍相乘，使得效率更高。任何一个数的幂都可以看作二进制来计算。

ll ksm(ll a,ll n){ll r=1;while(n!=0){if(n&1){r*=a;}a=a*a;n=n>>1;}return r;
}

简单应用：

• 计算a^n mod m
• 计算斐波那契数列第n项
• 将线性变换重复n次

注：矩阵的乘法计算

2、链式前向星举例

2.1、图

关于图的定义方式：

struct Edge {int next; // 下一条边的编号int to;   // 这一条边的终点int w;    // 权值
} e[maxn];

一般的输入方式都是：u -> v w 边 边 权

ll tot, head[maxn];
void add(ll u, ll v, ll w) {++tot; // 加入一条新边的编号e[tot].next = head[u]; // 新的边插在原来的第一个位置，所以next指向原来的head[u]e[tot].w = w;e[tot].to = v; // 下一条边head[u] = tot; // 新的边成为第一条变了
}

代码案例：

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
using ll = long long;
#define maxn 110001
struct Edge {int next; // 下一条边的编号int to;   // 这一条边的终点int w;    // 权值
} e[maxn];
ll tot, head[maxn];
void add(ll u, ll v, ll w) {++tot; // 加入一条新边的编号e[tot].next = head[u]; // 新的边插在原来的第一个位置，所以next指向原来的head[u]e[tot].w = w;e[tot].to = v; // 下一条边head[u] = tot; // 新的边成为第一条变了
}
int main() {IOS;// 添加边add(1, 2, 10);add(1, 3, 20);add(2, 4, 30);add(3, 4, 40);add(4, 5, 50);	// 打印图的邻接表for (int i = 1; i <= 5; ++i) {cout << "Vertex " << i << ": ";for (int j = head[i]; j != 0; j = e[j].next) {cout << "(" << e[j].to << ", " << e[j].w << ") ";}cout << endl;}return 0;
}

2.2、树

LCA问题

	int n;cin>>n;vector<vector<int>> graph(n+1);for(int i=1;i<n;i++){//n-1 条边int u,v;cin>>u>>v;graph[i].push_back(u);graph[i].push_back(v);//邻接矩阵}//倍增数组vector<array<int,21>> fa(n+1);//array<int,21> 固定的数组大小21vector<int> dep(n+1);//深度function<void(int,int)> dfs = [&](int x,int f){fa[x][0]=f;for(int i=1;i<=20;i++){fa[x][i]=fa[fa[x][i-1]][i-1];}//遍历数组for(const auto& tox:graph[x]){if(tox==f)continue;dep[tox]=dep[x]+1;dfs(tox,x);}};dfs(1,0);auto glca = [&](int x,int y){if(dep[x]<dep[y])swap(x,y);int d=dep[x]-dep[y];for(int i=20;i>=0;i--){if(d>>i & 1)x=fa[x][i];}if(x==y)return x;for(int i=20;i>=0;i--){if(fa[x][i] != fa[y][i]){x=fa[x][i];y=fa[y][i];}}return fa[x][0];};