自动搬运

查看原文

来自洛谷，原作者为

	DATA_X 入门赛T4击碎了我的AK梦

搬运于2025-08-24 23:15:00，当前版本为作者最后更新于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++： ```cpp #include #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) ``````$$