2023NOIP A层联测6 T2 冒泡排序趟数期望（bubble）

本文主要是介绍2023NOIP A层联测6 T2 冒泡排序趟数期望（bubble），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对于排列 $a[1\dots n]$ ，其进行一趟冒泡排序的代码如下：

for(int i=1;i<n;++i){if(a[i]>a[i+1]) swap(a[i], a[i+1]);
}

若排列在 $k$ 趟冒泡排序之后变为有序，则最小的 $k$ 定义为 $res$ 。
给一个长度为 $n$ 的随机排列（ $n!$ 种情况等概率出现），请你计算 $res$ 的期望值，对 $10^9+7$ 取模。

一般来说，冒泡排序和逆序对有很大的关系。

定义 $g_i=\sum\limits_{j=1}^{i-1}[a_j>a_i]$ ， $g_i$ 的意义是位置在 $i$ 前面，比 $a_i$ 大的数的个数。

$g_i$ 有很好的性质：

$g_i\in[0,i-1]$
每一个 $g$ 都唯一对应一个 $f$ 。（可以从后往前由 $g$ 构造出 $f$ ）

由性质 $2$ 得到 $g_i$ 能取遍 $[0, i - 1]$ 所有值。

模拟一下一趟冒泡排序的过程。对于一个 $a_i$ ，如果 $g_i$ 不为 $0$ ，则前面比 $a_i$ 大的某个数一定会与 $a_i$ 交换，从而 $g_i$ 减少 $1$ 。

排列有序后， $g_i$ 都为 $0$ 。要让所有 $g_i$ 变为 $0$ ，必然进行了至少 $max(g_i)$ 次排序。所以 $res=\max\limits_{i=1}^n(g_i)$

问题转换为枚举 $res=k(1\le k\le n)$ ，求满足 $\max\limits_{i=1}^n(g_i)=k$ 的 $g$ 的个数 $cnt_k$ 。

考虑构造 $g$ 。前面 $k$ 个位置可以任取，后面的位置 $g_i$ 要小于等于 $k$ ，至少要有一个 $g_i$ 等于 $k$ 。

即 $cnt_k=k!((k+1)^{n-k}-k^{n-k})$

答案即为 $\frac1{n!}\sum\limits_{k=1}^nk\cdot cnt_k$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int n;
ll f[1000001],inv[1000001];
ll ksm(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}
int main()
{freopen("bubble.in","r",stdin);freopen("bubble.out","w",stdout);f[0]=1;scanf("%d",&n);for(int i=1;i<=n;i++) f[i]=f[i-1]*i%mod;inv[n]=ksm(f[n],mod-2);for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;ll ans=0;for(int i=1;i<=n;i++){ans=(ans+i*f[i]%mod*(ksm(i+1,n-i)-ksm(i,n-i)+mod))%mod;}cout<<ans*inv[n]%mod;
}