「2020-2021 集训队作业」Permutation 题解

核心思路

1. 容斥原理

设：

• $A$：至少有一个不动点
• $B$：至少有一个对称点

$$f_n = |A \cap B| = |U| - |\overline{A}| - |\overline{B}| + |\overline{A} \cap \overline{B}| $$

2. 分量计算

• $|U| = n!$
• $|\overline{A}| = D_n$（错排数）
• $|\overline{B}| = T_n$（无对称点排列数）
• $|\overline{A} \cap \overline{B}| = Q_n$（双重禁位排列数）

3. 递推关系

错排数：

$$D_n = (n-1)(D_{n-1} + D_{n-2}), \quad D_0=1, D_1=0 $$

无对称点排列数（$n$ 为偶数）：

$$T_n = \sum_{k=0}^{n/2} (-1)^k \binom{n/2}{k} (n-2k)! $$

双重禁位排列数：

$$Q_n = (n-3)Q_{n-1} + (n-4)Q_{n-2} - (n-2)Q_{n-3} - Q_{n-4} $$

4. 最终计算

$$f_n = n! - D_n - T_n + Q_n \pmod{P}$$ $$\text{ans} = \bigoplus_{i=1}^n f_i$$

---