题解：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 代码：

CPP

#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);
}

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

文章操作

相关推荐

评论

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