牛客小白月赛 61 E 排队

题目

alt

样例

3
1 2 3

思路

from 机房学长

翻译题目

$n$ 个体总共有 $n!$ 种排队方式，记 $P_{i} (a)$ 表示序列 $a$ 的第 $i$ 种排队方式， $c n t (P i (a))$ 表示 $P_{i}$ 的逆序对个数。PLMM 想知道 ${\textstyle \sum_{i=1}^{n!}} cnt(Pi(a))$

给定一个 $n$ 个数，在所有排列顺序中，每种排列的分别的逆序对总数的总数是多少

所以我们根据题意就能写出简单暴力版code

简单暴力版 code $O (N! (N l o g N))$

// 帮助李姐题意
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 12, mod = 1e9 + 7;

int n, w[N];

int countInv(int w[])
{	// 具体的根据数组求数组逆序对方法
    // 可以用归并排序或者树状数组实现 O(nlogn)
    int cnt = 0;
    ......
	return cnt;
}

signed main()
{
	cin.tie(0) -> sync_with_stdio(0); 
	
	cin >> n;
	for (int i=1;i <= n;i ++ ) cin >> w[i];
	sort(w+1, w+1+n);
	
	int ans = 0;
	do
	{
		ans += countInv(w); // 计算每次的逆序对
		ans %= mod;
	}
	while (next_permutation(w+1, w+1+n)); // 根据字典序生成下一个
	cout << ans;
	
	return 0;
}

妥妥T飞，考虑优化。我们注意到可以根据，每一组逆序对对总数的贡献，大概方向就是每一组逆序对出现的次数对于答案的影响。

计算贡献

毫无疑问的是，对于互不相等的两数 $(a, b)$ ，满足 $a > b$ ，显然 $(a, b)$ 成为逆序对，当且仅当a出现在b之前。所以我们注意到：在 $n!$ 次排列下，要么 $a$ 在 $b$ 前面，要么 $b$ 在 $a$ 前面，且两种情况出现的概率都为 $\frac{1}{2}$ 。所以我们对于互不相同的一组 $(a, b)$ ，计算 $(a, b)$ 的所有排列情况并乘上 $\frac{1}{2}$ 即可。

具体如何计算 $(a, b)$ 呢？

对于 $a$ ，在未确定位置的 $n$ 个数中它的摆放可以是 $n$ 种
对于 $b$ ，在未确定的 $n - 1$ 个数中它的摆放可以是 $n - 1$ 种
除以 $2$ ，我们只需要大的数在前面的情况
剩下的 $n - 2$ 个数，全排列即可 $(n - 2)!$

若已经确定了所有互不相同的数对 $c n t$ ，我们只需要

\sum_{i=1}^{cnt} [\frac{n*(n-1)}{2} *(n-2)!] \bmod (10^9+7)

对应的 $c o d e$ 为

int A(int x)
{	// 返回x的阶乘 注意取模
    return 0;
}

int ans = 0, cnt;
for (int i=1;i <= cnt;i ++ )
	ans += (n*(n-1)/2)%mod * A(n-2) %mod;
cout << ans;

我们发现每次都是乘上一样的值，所有我们有

cnt * [\frac{n*(n-1)}{2} *(n-2)!] \bmod (10^9+7)

int A(int x)
{	// 返回x的阶乘
    return 0;
}
int put = (n*(n-1)/2)%mod * A(n-2) % mod;
cout << (cnt*put+mod)%mod;

求互不相同的数对组数 $c n t$

对于任何求出 $c n t$ ，我们可以 $s o r t$ 一遍，那么对于所有 $a i$ 我们累加上严格小于 $a i$ 的个数即可。

注意，这里必须是严格小于，而不是总数减去值等于 $a i$ 的所有数个数。很容易想到这是为什么，因为假设我们现在统计到了 $5$ , 且 $5$ 前面有 $3$ ，那么不同数的组数 $(3, 5)$ 对于 $c n t$ 只贡献了一次，我们在统计 $3$ 的时候就不能算上 $(3, 5)$ ，我们简单规定只要往前统计即可 (我就错在了这里QAQ)

并且我们预处理1到n的阶乘，进一步优化，于是我们得到了最终代码

人畜无害的代码：

#include <iostream>
#include <algorithm>
#define int long long

using namespace std;

const int N = 1e5 + 12, mod = 1e9 + 7;

int n, w[N];
int f[N*2];

signed main()
{
	cin.tie(0) -> sync_with_stdio(0);
	
	f[1] = 1;		// 预处理阶乘
	for (int i=2;i <= N;i ++ )
		f[i] = f[i-1] * i % mod;
	
	cin >> n;
	for (int i=1;i <= n;i ++ ) cin >> w[i];
	sort(w+1, w+n+1);
	
	if (n == 1) return cout<<0, 0;
	
	int cnt = 0; 	// 统计不同对数 
	for (int i=1;i <= n;i ++ )
	{
		int fid = lower_bound(w+1, w+1+n, w[i]) - (w+1);
		cnt += fid; // 注意下标
	}
	
	// 注意这里要先除2再模mod 
	int put = (n*(n-1)/2)%mod * f[n-2] % mod;
	
	cout << (cnt*put+mod)%mod;
	
	return 0;
}

题解 | 小白月赛61 排队