题解：P12369 [蓝桥杯 2022 省 Python B] 全排列的价值

· · 题解

可能更好的阅读体验

思考价值的本质是什么，发现其实就是把逆序对数换了个说法嘛。所以题目其实是让我们求长度为 n 的所有排列的逆序对数总和。

直接求肯定是不行的，考虑如何快速计算答案。发现答案可以分拆为两个子问题答案的乘积：求解单个数对贡献以及数对的数量。

考虑单独计算数对 (i,j) 产生的贡献。由于 i 和 j 的相对位置可以自由变换，所以 (i,j) 有 \dfrac{1}{2} 的概率是逆序对。全排列总数为 n!，那么 (i,j) 的贡献即为 \dfrac{n!}{2} 啦。

接下来考虑这样的数对一共有多少个。这其实等价于求在 n 个互不相同的小球中选 2 个小球的方案数，即 \displaystyle \binom{n}{2}=\dfrac{n!}{2!(n-2)!}=\dfrac{n(n-1)}{2}。

于是答案为：ans=\dfrac{n!}{2}\times \dfrac{n(n-1)}{2}=\dfrac{n!n(n-1)}{4}。

阶乘部分预处理即可，除法用费马小定理算逆元。注意取模要勤快。

附 AC 代码：

#include<bits/stdc++.h>
#define int long long
#define _ 0
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
int n;
int fac[N];//阶乘 
int qp(int a, int b, int p)//快速幂 
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
void initfac()//预处理阶乘 
{
    fac[0] = 1;
    for(int i = 1; i < N; i ++)
        fac[i] = fac[i - 1] * i % mod;
}
signed main()
{
    initfac();
    cin >> n;
    cout << fac[n] * n % mod * (n - 1) % mod * qp(4ll, mod - 2, mod) % mod;
    return (0^_^0);
}