倍增专题

P1306 斐波那契公约数

一个重要性质： g c d ( f [ n ] , f [ m ] ) = f [ g c d ( n , m ) ] gcd(f[n],f[m])=f[gcd(n,m)] gcd(f[n],f[m])=f[gcd(n,m)]，然后就矩阵快速幂加速即可。

具体说明见下面的文章。

https://harris.blog.csdn.net/article/details/115028278

---

P1383 高级打字机

主席树，需要动态维护一个子树大小，然后更新和查询就是基本操作了。

---

P1383 高级打字机(PST)

P S T PST PST板子题，每次更新时需要维护每个结点的子树大小，然后查询的时候就根据子树大小查询。对于删除操作就是将当前版本赋值为 r t [ i d − x − 1 ] rt[id-x-1] rt[id−x−1]就行了。

---

P1967 [NOIP2013 提高组] 货车运输

题意

给定 n n n个点 m m m条边的无向图，每条边有边权，给定 q q q个询问，每个询问包括一个起点，终点，求该路径的最大承重(即所有路径的最小值中最大的一个)

思路

M S T MST MST+树上倍增的好题。

贪心得考虑问题，显然是都用权值较大的边更优，所以构造一棵最大生成树，然后对于每个路径 s t → e d st\rightarrow ed st→ed，显然这条路径在树上就是 s t − → l a c ( s t , e d ) → e d st-\rightarrow lac(st,ed)\rightarrow ed st−→lac(st,ed)→ed

因此可以考虑树上倍增来找到路径上的最小值，就是在倍增父亲的时候同时会维护最小值即可。

P3509 [POI2010]ZAB-Frog

i i i增大 l l l不减，同时 r r r不减，所以可以用滑动窗口维护一个区间长为 k + 1 k+1 k+1的 [ l , r ] [l,r] [l,r]，然后用类似快速幂倍增即可。

P4281 [AHOI2008]紧急集合 / 聚会

倍增LCA，答案取两两LCA的三个点中不同的那个点，然后利用深度求和即可。

P4427 [BJOI2018]求和

求路径上结点深度的 k k k次方之和，由于k较小 可以预处理，树上每个结点到根的 k k k次方之后 ，然后倍增 L C A LCA LCA即可。

P6569 [NOI Online #3 提高组] 魔法值

矩阵快速幂&倍增优化。

考虑将结点变为 n × n n\times n n×n的转移矩阵，然后我们要维护的就是 1 × n 1\times n 1×n的目标矩阵，转移矩阵 a i j a_{ij} aij​如果 i , j i,j i,j相连就为 1 1 1，否则为 0 0 0，然后类似矩阵乘法，把求和改为异或和，因为是 01 01 01矩阵，在该条件下快速幂的正确性是有保证的。

时间复杂度： 32 n 3 + n 2 l o g x 32n^3+n^2logx 32n3+n2logx