这是倍增。
by FloatingIsland68 @ 2024-01-10 21:34:08
代码长得有点像倍增的 dp，但不算 dp，这题使用倍增加速模拟的过程
by Iniaugoty @ 2024-01-10 21:41:00
@[gty314159](/user/768612) 确实。但是根据DP的定义来说，是将特定条件的问题分成各子问题，从这个角度，有没有dp的存在呢
by Rex_Lapis @ 2024-01-10 22:25:57
@[Rex_Lapis](/user/432566) **我认为**，不存在（但有一点 DP 的思想），好比 ST 表、倍增 LCA 之类的预处理，这最多只能算上是一个递推，毕竟 OI-wiki 好像也说过，OI 中经常把一些严格意义上不是 DP 的递推当成 DP。
by Iniaugoty @ 2024-01-10 22:57:40
@[gty314159](/user/768612) 有一点DP的思想我也同意。李煜东的《算法竞赛》，上面写“ST算法”也可以用倍增优化DP来理解。那其实递推和DP的界限就有些模糊。
by Rex_Lapis @ 2024-01-10 23:10:00
@[Rex_Lapis](/user/432566) 我认为无所谓，毕竟会做就行了，不过还是建议不要看成 dp，因为 dp 太多了，这种偏模拟的 dp 并不好归类。
by mxzhang @ 2024-01-22 15:19:08