题解 | #少爷的秘境#

L题题解

该题要求求出最多$10^{18}10^\{18\}$步操作后的位置，但是首先实际上环上的位置是有限的，其次每个点的下一步会到的位置是固定的，所以我们在走至多$2n2n$步后，我们的行动轨迹一定成环

先暴力处理当前位置x和已经走的步数cnt，每走一步就使$x=(a+1)\times x+bx=(a+1)\; \backslash times\; x\; +\; b$，并存下到达当前x花费的步数$m{p}_x=cntmp\_x=cnt$，如果当前的x已经被走过，那么循环节的长度就是$cnt-m{p}_{x}cnt-mp\_x$，在找到循环节后再暴力走$(m-cnt)\mathrm{\%}(cnt-m{p}_x)\mathrm{步}\mathrm{即}\mathrm{可}(m-cnt)\backslash \%(cnt-mp\_x)步即可$

AC代码https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60102007