专栏文章

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

__DATA_X_
P12369题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip8771c
此快照首次捕获于
2025/12/03 07:45
3 个月前
此快照最后确认于
2025/12/03 07:45
3 个月前
查看原文

P12369 题解

题目大意：

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

公式推导：

给定一个排列 A=(a1,a2,...an)A=(a_1,a_2,...a_n) ，其价值定义为：
A=∑i=1n CiA= \sum_{i = 1}^{n} \ C_i
其中 CiC_i 是 a1a_1 到 ai−1a_{i-1} 中小于 aia_i 的数的个数。

推导过程：

顺序对的定义：

  • 对于排列 AA，顺序对是指满足 i<ji<j 且 ai<aja_i<a_j 的对 (i,j)(i,j)。
  • 每个顺序对 (i,j)(i,j) 会贡献到 CjC_j 的值中。

顺序对的总数：

  • 在所有排列中，顺序对 (i,j)(i,j) 出现的概率是 12\frac{1}{2}，因为 aia_i 和 aja_j 的大小关系是等概率的。
  • 总共有 (n2)=n(n−1)2\begin{pmatrix} n \\ 2 \\ \end{pmatrix}=\frac{n(n-1)}{2} 个可能的位置对。
  • 因此，所有排列中顺序对的总数为：
(n2)×n!×12=n(n−1)2×n!×12=n(n−1)×n!4\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}

价值之和：

  • 每个顺序对的价值为 n×(n−1)4\frac{n\times (n-1)}{4}。
  • 总共有 n!n! 个顺序对，价值之和为 n!×n×(n−1)4\frac{n!\times n\times (n-1)}{4}。
  • 由于结果可能很大，我们需要对 998244353998244353 取模。注意到 14 mod 998244353\frac{1}{4}\bmod 998244353 的逆元是 748683265748683265，因为 4×748683265≡1(mod998244353)4\times 748683265\equiv1 \pmod{998244353} 。 因此，最终公式为：
n!×n×(n−1)×74868326 mod 998244353 n!\times n\times (n-1)\times 74868326\bmod 998244353 ## 主要思路： 首先读取整数 $n$，如果 $n<2$ 直接输出 $0$ 并结束程序，否则计算 $n$ 的阶乘 $sum$（每次计算都取模防止溢出），最后套公式计算并输出结果。 ## 代码实现： ~~码风很烂，dalao 勿喷。~~ ### C++： ```cpp #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： ```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) ``````

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...