2025年倍增应用之倍增Floyd

科技前沿 • 2025-03-01 13:54 • 阅读 56

大家好，我是讯享网，很高兴认识大家。

首先总结一下倍增：

倍增是与二分相对应的一种算法，但两者不完全互为逆运算，其中，二分的要点是尽可能平均将区间划分开，而倍增则更多运用到二进制编码。

一般来说，倍增的思路主要是先预处理出1对应的数据，再用1对应的数据倍增得到2^p的数据，对于任意一个数m，就可以用预处理用二进制编码组合出m对应的数据。

例如，11的在二进制下编码是1011，那么11所对应的数据就可以由8+0+2+1得出，如果我们定义g( p )为2^p对应的数据，那么，f(11)=g(3)+g(1)+g(0)，其中，f(n)是不需要显式地算出来的，只需要调用g( p )求解即可。

伪代码如下：

int tmp=0; while(q){ 
    if(q&1) 组合的操作； //调用的是g[tmp] q>>=1; tmp++; }

讯享网

有了倍增的基础思想，进入今天的主题：

以下是一个倍增Floyd问题：

讯享网

给定一张图，求其中恰好经过m条边有多少种方案（n<=200,m<=10^9）

首先思考基础的状态定义和转移：
定义f(p,i,j)表示经过p条边，从i到j能够获得的最大权值。
状态转移：f(p,i,j)=Σ（ f(p-1,i,k) * f(p-1,k,j) ）。
外层枚举p，内层进行基础的Floyd，时间复杂度为O(n³m)，显然是难以接受的。

运用倍增的思想：
不再通过p-1转移到p，而是尽可能通过p/2转移到p。
定义g(q,i,j)为通过2^q条边，从i到j能获得的最大权值。
状态转移g(q,i,j)=Σ（ g(q-1,i,k) * g(q-1,k,j) ）。
外层循环的复杂度变成了logn，可以被接受。
最后再利用二进制编码组合出f(m)。

代码：

讯享网#include<cstdio> #include<cstring> #include<algorithm> //倍增思想： //状态转移时，将第i步看成是i/2步和i/2步转移而来，仅当i是偶数时，看成i-1和1步转移 //这样一来，利用m的二进制编码可将复杂度降低  const int maxn=110; typedef long long ll; const int mod=; int n; ll m; struct Mat{ 
    ll data[110][110]; ll* operator[](int x){ 
   return data[x];} //使Mat支持被下标访问  friend Mat operator*(Mat& a,Mat& b){ 
    //定义了矩阵乘法，也就是使两个不同的状态矩阵可以被合并  Mat c; for(int i=1;i<=n;i++){ 
    for(int j=1;j<=n;j++){ 
    c[i][j]=0; for(int k=1;k<=n;k++){ 
    c[i][j]=(c[i][j]%mod+(a[i][k]%mod*b[k][j]%mod)%mod)%mod; } } } return c; } void print(){ 
    for(int i=1;i<=n;i++){ 
    for(int j=1;j<=n;j++) printf("%lld ",data[i][j]); putchar('\n'); } } }f[100],A,ans; int main(){ 
    int cnt=0; scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++){ 
    for(int j=1;j<=n;j++){ 
    scanf("%lld",f[0][i]+j); } } for(cnt=0;cnt<=65;){ 
    //与倍增的快速幂一样，先预处理出2^P的数据，然后按照m的二进制编码进行调用  f[cnt+1]=f[cnt]*f[cnt]; cnt++; } bool get=false; int tmp=0; while(m){ 
    //二进制组合出m if(m&1){ 
    if(!get){ 
    ans=f[tmp]; get=true; } else ans=ans*f[tmp]; } m>>=1; tmp++; } //走m步  ll res=0; for(int i=1;i<=n;i++) res=(res+(ans[1][i])%mod)%mod; printf("%lld",res%mod); return 0; }

2.5.5.3

2025年倍增应用之倍增Floyd

首先总结一下倍增：

有了倍增的基础思想，进入今天的主题：

相关推荐