计数练习 Perm
题面
统计有多少 $m$ 阶排列比自己的逆排列的字典序小 .
即 $q(p)_{p_i} = i$ 并且存在一个 $i$ 使得 $\forall 1 \le j < i$ , $p_j = q(p)_j$ 且 $p_i < q(p)_i$ .
解题思路
排列的逆变换是有规律的 , 即 $q(q(p)) = p$ . 从 $p$ 和 $q(p)$ 来看 , 有关字典序的关系是相反的 , 所以只要 $q(p) \not = P$ , $(P , q(P))$ 就会对答案产生贡献 .
统计 $n$ 阶排列的数量 , 发现所有轮换大小不超过 2 的排列的逆排列就是它自己 . 记这样的 $n$ 阶排列的数量为 $f_n$ . 则 :
$$f_n = f_{n - 1} + (n - 1) \times f_{n - 2}$$
$$v_i = \dfrac{(i! - f_i)}{2}$$