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

_DATA_X_ · 2025-05-23 11:38:58 · 题解

P12369 题解

题目大意：

给你一个 n，求 n 的全排列中所有逆序对之和。

公式推导：

给定一个排列 A=(a_1,a_2,...a_n) ，其价值定义为：

A= \sum_{i = 1}^{n} \ C_i

其中 C_i 是 a_1 到 a_{i-1} 中小于 a_i 的数的个数。

推导过程：

顺序对的定义：

对于排列 A，顺序对是指满足 i<j 且 a_i<a_j 的对 (i,j)。
每个顺序对 (i,j) 会贡献到 C_j 的值中。

顺序对的总数：

在所有排列中，顺序对 (i,j) 出现的概率是 \frac{1}{2}，因为 a_i 和 a_j 的大小关系是等概率的。
总共有 $ \begin{pmatrix} n \ 2 \ \end{pmatrix}=\frac{n(n-1)}{2}
因此，所有排列中顺序对的总数为：

\begin{pmatrix} n \\ 2 \\ \end{pmatrix}\times n! \times \frac{1}{2}=\frac{n(n-1)}{2}\times n! \times \frac{1}{2}=\frac{n(n-1) \times n!}{4}

价值之和：

每个顺序对的价值为 \frac{n\times (n-1)}{4}。
总共有 n! 个顺序对，价值之和为 \frac{n!\times n\times (n-1)}{4}。
由于结果可能很大，我们需要对 998244353 取模。注意到 \frac{1}{4}\bmod 998244353 的逆元是 748683265，因为 4\times 748683265\equiv1 \pmod{998244353} 。因此，最终公式为： n!\times n\times (n-1)\times 74868326\bmod 998244353 ## 主要思路：

首先读取整数 n，如果 n<2 直接输出 0 并结束程序，否则计算 n 的阶乘 sum（每次计算都取模防止溢出），最后套公式计算并输出结果。

代码实现：

~~码风很烂，dalao 勿喷。~~

C++：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=748683265;//mod 的模逆元
int n;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    if(n<2)//特判{
        cout<<0<<endl;
        exit(0);
    }
    int sum=1;//阶乘
    for(int i=1;i<=n;i++){
        sum=sum*i%mod;
    }
    cout<<sum*n%mod*(n-1)%mod*N%mod;//打印结果。
    return 0;
}

Python：

OD = 998244353

n = int(input())
if n == 1:
    print(0)
    exit()

fact = [1] * (n + 1)
for i in range(1, n + 1):
    fact[i] = fact[i - 1] * i % MOD

inv_fact = [1] * (n + 1)
inv_fact[n] = pow(fact[n], MOD - 2, MOD)
for i in range(n - 1, -1, -1):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

def comb(a, b):
    if a < 0 or b < 0 or a < b:
        return 0
    return fact[a] * inv_fact[b] % MOD * inv_fact[a - b] % MOD

res = 0
for k in range(1, n + 1):
    term = comb(n, k) * fact[k - 1] % MOD
    term = term * fact[n - k] % MOD
    term = term * (k * (k - 1) // 2) % MOD
    res = (res + term) % MOD

print(res)