网站需要哪些东西,网站建设课程大纲,各大网站发布信息,金华市网站建设倍增 倍增算法是一种优化算法#xff0c;通常用于某些需要高效计算指数幂的场景。它基于分治的思想#xff0c;通过反复求平方来实现快速计算指数幂的目的。在实际应用中#xff0c;倍增算法经常用于解决最近公共祖先问题、二分查找等。 1、快速幂详解 ksm核心代码 倍增就是…倍增 倍增算法是一种优化算法通常用于某些需要高效计算指数幂的场景。它基于分治的思想通过反复求平方来实现快速计算指数幂的目的。在实际应用中倍增算法经常用于解决最近公共祖先问题、二分查找等。 1、快速幂详解 ksm核心代码 倍增就是基于二进制的指数倍相乘使得效率更高。任何一个数的幂都可以看作二进制来计算。
ll ksm(ll a,ll n){ll r1;while(n!0){if(n1){r*a;}aa*a;nn1;}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; // 新的边成为第一条变了
}代码案例
#includebits/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;cinn;vectorvectorint graph(n1);for(int i1;in;i){//n-1 条边int u,v;cinuv;graph[i].push_back(u);graph[i].push_back(v);//邻接矩阵}//倍增数组vectorarrayint,21 fa(n1);//arrayint,21 固定的数组大小21vectorint dep(n1);//深度functionvoid(int,int) dfs [](int x,int f){fa[x][0]f;for(int i1;i20;i){fa[x][i]fa[fa[x][i-1]][i-1];}//遍历数组for(const auto tox:graph[x]){if(toxf)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 ddep[x]-dep[y];for(int i20;i0;i--){if(di 1)xfa[x][i];}if(xy)return x;for(int i20;i0;i--){if(fa[x][i] ! fa[y][i]){xfa[x][i];yfa[y][i];}}return fa[x][0];};
