题解：AT_arc219_b [ARC219B] Reverse Permutation

沉石鱼惊旋 · 2026-05-13 13:00:08 · 题解

感觉对着样例拟合一下就过了。你考虑一个排列如何操作一次变得字典序最小，如果 p_1\neq 1 必须换 [1,pos_1]。如果 p_1=1,p_2\neq 2 必须换 [2,pos_2]，这样子。除非排列本身就是 1,2,\dots,n，随便选一个 [i,i]。

我们考虑给定排列 q 他是被怎么换的，如果 q_1=1 那么可能是后面 n-1 个位置，每个在原排列上都可能是 1，就有 n-1 个换法。q_2=2 同理，可能 p_1=1，后面 n-2 个位置换过来的。以及如果 q 本身就是 1,2,\dots,n，p 还有 1,2,\dots,n 的可能，答案再加 1。

https://atcoder.jp/contests/arc219/submissions/75698092