「Counting Swaps」计数交换

形式化题目

给定一个 $1\sim n$ 的排列 $p$ ，一次操作是任选两个位置交换它们的值。设把 $p$ 变成恒等排列 $1,2,\dots,n$ 至少需要 $m$ 次交换，求长度恰为 $m$ 的操作序列条数（操作顺序不同算不同方案），对 $10^9+9$ 取模。

先看样例 $p=2\ 3\ 1$ 。把它按「值 $\to$ 下标」连边，得到一个长度为 $3$ 的轮换：

位置 $i$	1	2	3
$p_i$	2	3	1
$p_i \to i$	$1\leftarrow 2$	$2\leftarrow 3$	$3\leftarrow 1$

flowchart LR
  A((1)) -- "p₁=2" --> B((2))
  B -- "p₂=3" --> C((3))
  C -- "p₃=1" --> A

（沿箭头看：位置 1 的值 2 应去位置 2，位置 2 的值 3 应去位置 3，位置 3 的值 1 应去位置 1，三者构成一个 3-环。）轮换个数 $k=1$ ， $n=3$ ，所以 $m=3-1=2$ ；题面给出的 3 种两步方法正对应这个环的 3 种「拆法」。

正解

思路

第一步：最少交换次数 $m$ 是多少？

把排列分解成轮换（不动点也算长度为 1 的轮换），设轮换个数为 $k$ 。交换两个位置 $x,y$ 时：

若 $x,y$ 在同一个轮换里：这个环被分裂成两个环， $k$ 增加 $1$ ；
若 $x,y$ 在不同轮换里：两个环合并成一个， $k$ 减少 $1$ 。

flowchart LR
  subgraph S["同一环：交换 (1,3) → 分裂"]
    direction LR
    a1((1)) --- a2((2)) --- a3((3))
  end
  subgraph T["分裂后"]
    direction LR
    b1((1)) --- b2((2))
    b3((3))
  end
  S -- "+1 个环" --> T

图中 3-环 $\{1,2,3\}$ 在环内交换一次后断成 $\{1,2\}$ 与 $\{3\}$ ：环内交换的效果就是把环剪成两段。而目标状态 $1,2,\dots,n$ 恰有 $n$ 个轮换（全是长度 1），所以任何方案都至少需要 $n-k$ 步；另一方面，不断在环内交换总能一步步把环剪碎，达到 $n-k$ 步。于是

m = n - k.

第二步： $m$ 步的方案长什么样？

关键约束：合并步不允许出现。若方案中出现一次「合并」（ $k$ 减 1），那么之后还得多用一步把它分裂回来，总步数必然超过 $n-k$ 。因此每个 $m$ 步方案里每一步都是分裂，于是：

长度为 $c$ 的轮换在整个方案中恰被分裂 $c-1$ 次；
不同轮换的操作互不干扰，操作集合可以按组划分。

第三步：只数每一组的「分裂序列」。

把整个方案逆过来看：把 $p$ 排好序的一串分裂，逆过来就是把 $c$ 个元素用 $c-1$ 次对换合并成一个 $c$ -轮换。这正是经典结论（Dénes 定理，其组合证明即 Cayley 公式 $c^{c-2}$ ）：

固定 $c$ 个元素，把它们用 $c-1$ 个对换的乘积表出某一个 $c$ -轮换的有序方式数恰为 $c^{c-2}$ 。

所以每组贡献 $c^{c-2}$ 种。最后是组间的穿插： $m$ 个操作分属各组，同组内的相对顺序已被 $c^{c-2}$ 定死，而组与组之间可以任意穿插，共有多重排列数

\frac{m!}{\prod_i (c_i-1)!}

种排法。合在一起，把每组的 $\dfrac{1}{(c_i-1)!}$ 分摊回去：

\boxed{\ \text{ans} = m! \prod_{c_i>1} \frac{c_i^{\,c_i-2}}{(c_i-1)!} \pmod{10^9+9}\ }

用三个样例核对一下闭式：

排列	轮换长度	$m$	计算	答案
$2\ 3\ 1$	$\{3\}$	2	$2!\cdot\dfrac{3^1}{2!}$	3
$2\ 1\ 4\ 3$	$\{2,2\}$	2	$2!\cdot\dfrac{2^0}{1!}\cdot\dfrac{2^0}{1!}$	2
$1\ 2$	$\varnothing$	0	$0!=1$	1

与题面输出完全一致。实现上只需：读入后 $O(n)$ 找出所有轮换长度，再对每个 $c>1$ 做一次快速幂 $c^{c-2}$ 和一次费马小定理逆元 $((c-1)!)^{-1}$ ，全部乘起来。注意模数是 $10^9+9$ （质数），不是常见的 $10^9+7$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 16:27
# update_at: 2026-10-01 16:27

import sys
from math import factorial

MOD = 10**9 + 9


def cycle_lengths(p: list[int]) -> list[int]:
    """排列每个轮换的长度（不含长度 1 的不动点，它们不参与任何交换）。"""
    n = len(p)
    seen = [False] * n
    return [length
            for start in range(n)
            if not seen[start]
            for length in [walk_cycle(start, p, seen)]]


def walk_cycle(start: int, p: list[int], seen: list[bool]) -> int:
    """从 start 沿置换走一圈，标访问并返回这一圈的长度。"""
    length = 0
    j = start
    while not seen[j]:
        seen[j] = True
        j = p[j] - 1  # p 存的是 1-based 的值，走的是「值 → 下标」这一步
        length += 1
    return length


def count_min_swaps(n: int, p: list[int]) -> int:
    """最少 m 次交换把 p 排好序的方案数。

    m = n - 轮换个数；每次交换使轮换个数恰好 +1（分裂），所以最短方案中
    每次交换都分裂一个轮换。逆着操作看是把 c 个元素合并成 c-轮换，由
    Dénes 定理（Cayley 公式）恰有 c^(c-2) 种合并方式；再乘上
    m 次操作的自由穿插 m!，除掉每组内部相对顺序 (c-1)!。
    """
    lengths = cycle_lengths(p)
    m = n - len(lengths)  # 最少交换次数
    ans = factorial(m) % MOD
    for c in lengths:
        if c > 1:
            ans = ans * pow(c, c - 2, MOD) % MOD              # 该组的合并方式数
            ans = ans * pow(factorial(c - 1), MOD - 2, MOD) % MOD  # 除以 (c-1)! 取模
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        n = next(data)
        p = [next(data) for _ in range(n)]
        out.append(str(count_min_swaps(n, p)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 18:35
 * update_at: 2026-10-06 18:35
 */
#include <cstdio>
using namespace std;

typedef long long ll;

const ll MOD = 1000000009;  // 题目要求的模数，注意不是常见的 1e9+7
const int MAXN = 100005;    // n 的最大规模

int p[MAXN];    // p[i] 表示排列第 i 个位置上的数值（下标从 1 开始）
int vis[MAXN];  // vis[i] 标记位置 i 是否已经在轮换分解中被走过
ll fact[MAXN];  // fact[i] = i! mod MOD

// 快速幂：计算 base^exp mod MOD。
ll mod_pow(ll base, ll exp) {
    ll res = 1 % MOD;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

// 预处理阶乘，供 m! 和 (c-1)! 使用。
void init_fact() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
}

void solve() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &p[i]);
            vis[i] = 0;
        }

        // 沿「位置 i -> 位置 p[i]」走，把排列分解成若干轮换。
        // 设轮换个数为 k，则最少交换次数 m = n - k；
        // 每个长度 c 的非平凡轮换贡献 c^(c-2) * ((c-1)!)^(-1)（Dénes 定理）。
        int cycle_count = 0;
        ll ans = 1;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) continue;
            int len = 0;
            int j = i;
            while (!vis[j]) {
                vis[j] = 1;
                j = p[j];
                len++;
            }
            cycle_count++;
            if (len > 1) {
                ans = ans * mod_pow(len, len - 2) % MOD;              // c^(c-2)
                ans = ans * mod_pow(fact[len - 1], MOD - 2) % MOD;    // 除以 (c-1)!
            }
        }

        ll m = n - cycle_count;      // 最少交换次数
        ans = ans * fact[m] % MOD;   // 再乘上 m 次操作的穿插方案数 m!
        printf("%lld\n", ans);
    }
}

int main() {
    init_fact();
    solve();
    return 0;
}

复杂度

时间复杂度：每组数据轮换分解 $O(n)$ ，每个非平凡轮换各一次 $O(\log c)$ 快速幂，合计 $O(n \log n)$ 上界；读入用一次性 read().split()。
空间复杂度： $O(n)$ ，排列数组和访问标记。

总结

这道题的骨架是「模型变换 + 组合计数」：先用轮换结构把「最少交换次数」变成 $m=n-k$ ，再用「最短方案中每步都是分裂」把方案按轮换分组，最后用 Dénes 定理（Cayley 公式的 $c^{c-2}$ ）收尾得到闭式。全程没有搜索、没有 DP，计数的关键在于找到那个可以逐组独立计数、再乘穿插数合并的分解方式。

图示解析

从轮换视角完整回放样例 $2\ 3\ 1$ 的方法二（先交换 $2,1$ ，再交换 $3,2$ ）：

步骤	操作	排列	轮换个数
初始	—	$2\ 3\ 1$	1（一个 3-环）
第 1 步	交换位置 1、2	$1\ 3\ 2$	2（3-环分裂出 $\{1\}$ ）
第 2 步	交换位置 2、3	$1\ 2\ 3$	3（全是不动点）

每一步环数都 $+1$ ，两步正好把唯一的 3-环拆成三个不动点——这就是「最短方案每步都在分裂」的具体样子。