-
分析
首先计算单个排列中的逆序对数量。
我们发现这东西可以分为两类，一类是两个数在原排列和倒着的排列（这里称为“反排列”），另一类是两个数一个在原排列，一个在反排列的。对于第一类，我们发现，原排列中的顺序对是反排列中的逆序对，所以原排列的所有数对要么在原排列中是逆序对，要么在反排列中是逆序对，所以原排列中的数对个数即为答案，即 \(\frac{n \times (n - 1)}{2}\)。
对于第二类，我们发现反排列中的任意数下标都大于正排列中的任意数，所以对于一个在反排列中的数 \(x\) 而言，下标小于它且大于它的数有 \(n - x\) 个，所以第二类的答案为 \(\sum_{i=1}^{n} n-i\)，转换一下即为\(\sum_{i=1}^{n-1} i\)，根据等差数列求和公式，原式的值为\(\frac{n \times (n - 1)}{2}\)。所以单个排列的逆序对数量为\(\frac{n \times (n - 1)}{2} + \frac{n \times (n - 1)}{2}=n \times (n - 1)\)。
一个数 \(n\) 的全排列共有 \(n!\) 种，所以最后的答案为\(n! \times n \times (n - 1)\)。
-
代码
#include <iostream>
#define int long long
using namespace std;
constexpr int MAXN(1000007);
constexpr int mod(1000000007);
int fct[MAXN];
int T, n;
inline void read(int &temp) { cin >> temp; }
inline void work() {
read(n);
cout << (fct[n] * n % mod * (n - 1) % mod) % mod << endl;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
fct[0] = 1;
for (int i(1); i <= 100000; ++i) fct[i] = fct[i - 1] * i % mod;
read(T);
while (T--) work();
return 0;
}