Problem J39: Inversion Sum of Previous Permutations / 逆序对数

版权信息：

任务总览

题目描述

Tom 已经掌握了计算一个排列中逆序对的数量。但现在老师提出了一个更难的问题：

给定一个 $1 \sim n$ 的排列 $P$，请你计算 ​ 所有字典序比 $P$ 小的排列的逆序对数之和 ​。

你需要对结果取模 $10 ^ 9 + 7$ 后输出。

输入格式

输入包含多组数据（不超过 20 组）。

每组数据格式如下：

• 第一行为一个正整数 $n$（$1 \leq n \leq 10 ^ 5$）；
• 第二行为 $n$ 个整数，表示 $1 \sim n$ 的一个排列。

输出格式

每组数据输出一行，表示所有字典序比当前排列小的排列的逆序对数之和，对 $10 ^ 9 + 7$ 取模。

输入输出样例

输入示例

3
2 1 3
5
2 1 4 3 5

输出示例

1
75

题目分析与解法

✅ 定义回顾

• ​ 逆序对数 ​：在一个排列中，满足 $i < j$ 且 $a_i > a_j$ 的 $(i, j)$ 对数；
• ​ 字典序小于 $P$ 的排列 ​：所有排在 $P$ 前的合法排列；
• 要求计算这些排列中所有逆序对数之和。

✅ 解法思路（组合数学 + 树状数组）

1. 对每一位进行枚举，假设当前位置选择比当前数小的数字 $k$；
2. 计算这些 $k$ 作为起点时能贡献的逆序对数量（前缀状态）；
3. 预处理阶乘与阶乘前缀和，快速计算字典序前缀方案数；
4. 使用树状数组维护已经出现过的数字，用于动态查询逆序对数量；
5. 整体按位推进，边算边更新。

时间复杂度分析