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

Aegleseeker_ · 2025-07-13 17:51:17 · 题解

一个常见的套路是，对于一个排列 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)。