题目大意
现在机器人有一种移动方式,问机器人从某一个起点到达 lil_ili rir_iri 位置。
题解思路
问题 111 我们现在机器人从 p0p_0p0 开始,走了一圈到达 p1p_1p1 ,那么 p1p_1p1 的位置会在哪里?
我们设白色节点的数目为 ttt ,那么我们可以到达 (p0+t)mod n(p_0 + t) \mod n(p0 +t)modn 位置。因为这次的移动,本质上是相当与 robotrobotrobot 顺时针走了 ttt 步。
问题 222 现在我们机器人最终到达了 lj,rjl_j , r_jlj ,rj ,那么对于 lj和rjl_j 和 r_jlj 和rj 有什么限制?
其中一个节点应该是最后一步走到的,我们设最后一步走的是顺时针,那么 rjr_jrj , 这个点似乎就相当于未生效。 这样我们可以找到这一圈的起始点 p1p_1p1 。
只后,我们可以从 p1p_1p1 开始模拟,机器人是否可以到底 lj,rjl_j, r_jlj ,rj 。
时间复杂度 O(n×mn \times mn×m)
参考代码