题解：P13280 「CZOI-R4」午夜巡游

一个常见的套路是，对于一个排列 $p$，我们连边 $i\rightarrow p_i$，可以形成若干个简单环，我们称之为置换环。

显然本题每次巡游后，$x$ 会在所在置换环中往后走一步。则最终的位置即为 $k$ 往后走 $L\bmod m$ 次所在的位置，其中 $L$ 为 $k$ 所在环长。

分两种情况讨论。

最终停留在 $k$：不难发现有 $\sum\limits_{1\le L\le n,m\bmod L=0}A_{n-1}^{L-1}\times (n-L)!$ 中合法的排列，将排列拆开后为 $(n-1)!\times \sum\limits_{1\le L\le n}[m\bmod L=0]$。

最终不停留在 $k$：同理枚举环长。对于每个最终停留位置，贡献是相等的，即 $(n-2)!\times \sum\limits_{1\le L\le n}[m\bmod L\neq0]$，乘上 $\frac{n\times (n+1)}{2}-k$ 即可。

我们预处理阶乘，复杂度可以做到 $O(n+q\sqrt m)$。