P10812船新图论做法

· · 题解

注意到一次如果不考虑往更大的数字的跳跃，显然可以建出一个有向无环图跑拓扑排序即可，因此我们考虑将原转移转换为有向无环图上的动态规划。

难点在 +1 操作上。

可发现，该操作只能与向因子移动组合在一起使用，不妨考虑在点 i 时可以向哪些 j 连接一条表示先进行若干次 +1 再进行一次走向因子的边。

容易发现，这与之前到过的最小的比 i 大的点有关。

考虑建分层图， id_{i,j} 表示当前在 i 点，之前到过的最小的比 i 大的点为 j 的点。

连边如下：

$id_{i,j}$ 连向 $id_{k,i}$，其中 $k\mid i$。 $id_{i,j}$ 连向 $id_{k,i}$ ，其中存在 $j-1\geq q\geq i+1$ 且 $k\mid q$。 前两者复杂度优秀，第三个可以后缀和优化建图。 然后发现空间超限了。 打表发现答案在 __int128 范围内，较大数据打表即可。