B. Emordnilap
A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). There are $n! = n \cdot (n-1) \cdot (n - 2) \cdot \ldots \cdot 1$ different permutations of length $n$.
Given a permutation $p$ of $n$ numbers, we create an array $a$ consisting of $2n$ numbers, which is equal to $p$ concatenated with its reverse. We then define the beauty of $p$ as the number of inversions in $a$.
The number of inversions in the array $a$ is the number of pairs of indices $i$, $j$ such that $i < j$ and $a_i > a_j$.
For example, for permutation $p = [1, 2]$, $a$ would be $[1, 2, 2, 1]$. The inversions in $a$ are $(2, 4)$ and $(3, 4)$ (assuming 1-based indexing). Hence, the beauty of $p$ is $2$.
Your task is to find the sum of beauties of all $n!$ permutations of size $n$. Print the remainder we get when dividing this value by $1\,000\,000\,007$ ($10^9 + 7$).
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.
Each test case has only one line — the integer $n$ ($1 \leq n \leq 10^5$).
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
Output
For each test case, print one integer — the sum of beauties of all permutations of size $n$ modulo $1\,000\,000\,007$ ($10^9 + 7$).
Example
input
3 1 2 100
output
0 4 389456655
Note
For the first test case of the example, $p = [1]$ is the only permutation. $a = [1, 1]$ has $0$ inversions.
For the second test case of the example, the permutations are $[1, 2]$ and $[2, 1]$. Their respective $a$ arrays are $[1, 2, 2, 1]$ and $[2, 1, 1, 2]$, both of which have $2$ inversions.
解题思路
比赛的时候想不出正解，然后模拟了几个样例找规律，发现任意一个排列逆序对的数量都相同，均是$n(n-1)$，因为一共有$n!$种排列，因此答案就是$n(n-1) \cdot n!$。
参考官方题解的推导。考虑排列中的两个下标$i$和$j$（$i < j$），在任意一个排列中他们形式一定是$[\dots p_i \ldots p_j \ldots p_j \ldots p_i \ldots]$ ，然后分情况讨论：
- $p_i > p_j$。那么排列中$p_i$对于$p_j$而言就存在$2$个逆序对。
- $p_i < p_j$。那么排列中$p_j$对于$p_i$而言就存在$2$个逆序对。
因此对于任意一对下标$i, j$都会存在两个逆序对，而一个排列中共有$C_{n}^{2}$对这样的下标，因此一个排列中的逆序对个数就是$2 \cdot C_{n}^{2}$。
由于有$n!$种不同的排列，故总的逆序对个数就是$2 \cdot C_{n}^{2} \cdot n! = n(n-1) \cdot n!$。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef long long LL;
5
6 const int mod = 1e9 + 7;
7
8 void solve() {
9 int n;
10 scanf("%d", &n);
11 int ret = (n - 1ll) * n % mod;
12 for (int i = 1; i <= n; i++) {
13 ret = 1ll * ret * i % mod;
14 }
15 printf("%d\n", ret);
16 }
17
18 int main() {
19 int t;
20 scanf("%d", &t);
21 while (t--) {
22 solve();
23 }
24
25 return 0;
26 }
参考资料
Codeforces Round #845 (Div. 2) and ByteRace 2023 Editorial：https://codeforces.com/blog/entry/111729
标签：10,排列,Emordnilap,cdot,permutation,test,逆序 From： https://www.cnblogs.com/onlyblues/p/17064291.html