Appearance
倍增能够使得线性的处理转化为对数级的处理,大大地优化时间复杂度
与其说倍增是算法,不如说它是一种思想,它能够帮助我们优化算法
不难看出,任意整数都可以被表示为若干个2的次幂项的和
因此我们可以把原问题划分为多个2次幂,常见的表示方法为
设 f(p,k) 表示在 p 点跳 2k 步
如果满足条件就令:
并且加上这次的 f(p,k) 的贡献
否则就:
直到 k=0 停止下来