题目理解

我们有一个 $1$ 到 $n$ 的排列，Johny 不断将其转换为字典序前驱排列，直到变成 $1,2,\ldots,n$。每次转换通过交换两个元素实现。我们需要计算总共的交换次数。

关键观察：从任意排列到单位排列的字典序递减序列中，总的交换次数等于所有排列的逆序数之和。

问题转化

设当前排列为 $p$，其字典序排名为 $k$（从 $0$ 开始计数，单位排列排名为 $0$）。

我们需要计算从排名 $k$ 的排列到排名 $0$ 的排列过程中所有排列的逆序数之和。

关键思路

1. 逆序数与排列排名的关系

对于一个排列，其排名可以分解为：

• 考虑第一个位置，如果该位置是第 $i$ 小的元素，那么有 $(i-1) \times (n-1)!$ 个排列比它小
• 然后递归考虑剩余部分

2. 交换次数分析

从样例可以看出：

• $(3,1,2)$: 逆序对为 $(3,1),(3,2)$，交换 2 次
• $(2,3,1)$: 逆序对为 $(2,1),(3,1)$，交换 1 次
• $(2,1,3)$: 逆序对为 $(2,1)$，交换 2 次
• $(1,3,2)$: 逆序对为 $(3,2)$，交换 1 次

结论：每次转换到前驱排列所需的交换次数等于当前排列的逆序数。

3. 数学推导

设 $f(k)$ 表示排名为 $k$ 的排列的逆序数。

总交换次数 = $\sum_{i=0}^{k-1} f(i)$

我们需要高效计算这个和。

算法核心

1. 逆序对贡献计算

对于位置 $i$，如果当前元素在剩余未使用元素中是第 $j$ 小的，那么：

• 它会产生 $j-1$ 个逆序对（与比它小的元素）
• 有 $(j-1) \times (n-i)!$ 个排列在这个位置有更小的元素

2. 预处理

代码中的关键数组：

• fac[i]: $i! \bmod M$
• inv[i]: $i!$ 的逆元
• s[i]: 前缀和数组，用于快速计算贡献

3. 树状数组维护

使用树状数组 t 来统计当前还有哪些元素未被使用，从而确定当前元素的排名。

代码详解

// 预处理阶乘和逆元
il void init() {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i)
        fac[i] = fac[i - 1] * 1ll * i % mod;
    inv[n] = qp(fac[n], mod - 2);
    for (int i = n - 1; i >= 0; --i)
        inv[i] = inv[i + 1] * (i + 1ll) % mod;
}

// 关键：计算s数组，用于快速计算贡献
for (int i = 1; i <= n; ++i)
    s[i] = (s[i - 1] + 1ll * (i - 1ll) * f(i) % mod * inv[i]) % mod;

// 从后往前处理排列
for (int i = n; i; --i) {
    // w 计算当前元素对总交换次数的贡献
    w = (1ll * s[n - i] * fac[n - i] + f(n - i + 1)) % mod;
    // 乘以当前元素的排名（比它小的未使用元素个数）
    ad(ans, 1ll * w * get(a[i]) % mod);
    // 标记当前元素已使用
    add(a[i], 1);
}

4. 函数 f(x) 的作用

il int f(int x) {
    return 1 + (x - 1) / 2;
}

这个函数计算的是：对于长度为 $x$ 的排列，平均逆序数的一个近似值。实际上，长度为 $n$ 的排列的平均逆序数是 $\frac{n(n-1)}{4}$。

时间复杂度

• 预处理：$O(n)$
• 主循环：$O(n \log n)$（树状数组操作）
• 总复杂度：$O(n \log n)$

算法正确性

该算法通过组合数学的方法，将总交换次数的计算转化为：

1. 对每个位置，计算其在不同排名下的逆序对贡献
2. 使用树状数组动态维护未使用元素的排名
3. 通过预处理的前缀和数组快速累加贡献

算法标签

• 组合数学
• 预处理
• 树状数组
• 逆序对
• 前缀和

总结

这道题的关键在于认识到总交换次数等于所有中间排列的逆序数之和，然后通过组合计数和数据结构高效计算这个和。算法巧妙地将问题分解，利用排列的字典序性质和逆序数的关系，实现了 $O(n \log n)$ 的解决方案。