介于$NH$ 老师暗示我做的题目太少，所以就有了这篇题解。

这种题一般都是一个排列作为置换，然后在某一个环上一直跑。

但是显然 $n$ 太大，我们不能直接把置换求出来，不过我们可以打表看看有无规律。

我们以$n=8$ 为例，置换序列如下：

1->5

2->1

3->6

4->2

5->7

6->3

7->8

8->4

然后你把这两个环画一下，发现我每一步都是乘了一个模 (n+1) 意义下2的逆元。

然后因为$2$ 是一个常数，我们注意到其逆元就是（n+2）>>1

然后就做完了。