2023NOIP A层联测6 冒泡排序趟数期望

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

题目大意

对于一个排列$a_1,a_2,\dots ,a_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$取模。

$1\le n\le 10^6$

题解

有一道思想类似的题，大家感兴趣的话可以看一下：8ady。

对于每趟冒泡排序，都是将一个数放在它后面离他最近的比它大的数前面。然而，我们并不知道会向后移多少，所以我们需要换一个方向思考。

对于所有满足$a_i<i$的$i$，最后$a_i$肯定是要被移到第$a_i$个位置。因为$a_i<i$，所以一定存在若干个（有可能只有一个，但至少有一个）$j<i$满足$a_j>a_i$，那么这些$j$中肯定有一个$j$在当前这这趟冒泡排序中与$i$互换，使得数字$a_i$被往前移了一个位置。所以，对于所有$a_i<i$，每趟冒泡排序一定且只会使数字$a_i$往前移一个位置，那么

r e s = max ⁡ i = 1 n { i − a i } res=\max\limits_{i=1}^n\{i-a_i\} res=i=1maxn​{i−ai​}

那么，对于我们需要算出对于每个$0\le k<n$，$res==k$的序列$a_i$的数量。

但是，直接计算$res==k$的序列$a_i$的数量不太好算，我们不妨来求$res\le k$的序列$a_i$的数量。

我们试着构造序列$a$，也就是将每个$1\le t\le n$填入序列$a$。$res\le k$，即$\forall 1\le i\le n$，都满足$i-a_i\le k$，也就是$i\le k+a_i$。那么，将$t$填到$a_i$中时（也就是令$a_i=t$），要满足$i\le k+t$，也就是说$t$只能填到$[1,\min (n,k+t)]$上。

我们从$t=1$到$n$将$t$填入$a$中。对于每个$t$，它本来是可以填$\min (n,k+t)$个位置的，但前面$t-1$个数可以填的区间都在$[1,\min (n,k+t)]$上，所以可填的位置只有$\min (n,k+t)-(t-1)$。

那么，$res\le k$的序列$a$的个数为$\prod _{t=1}^n[\min (n,k+t)-(t-1)]=(\prod _{t=1}^{n-k}k+1)\times (\prod _{t=n-k+1}^{n}n-t+1)=k!\times (k+1{)}^{n-k}$

设$V(k)=k!\times (k+1{)}^{n-k}$，设$v_k$表示$res==k$的序列$a_i$的数量，则$v_k=V(k)-V(k-1)$。

于是，答案为$\frac{\sum _{k=0}^{n-1}k\times v_k}{n!}$。

时间复杂度为$O(n\log n)$。

code

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
const int N=1e6;
int n;
long long ans=0,jc[N+5],ny[N+5],v[N+5];
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void init(){jc[0]=1;for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%mod;ny[N]=mi(jc[N],mod-2);for(int i=N-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;
}
int main()
{freopen("bubble.in","r",stdin);freopen("bubble.out","w",stdout);init();scanf("%d",&n);for(int k=0;k<n;k++){v[k]=jc[k]*mi(k+1,n-k)%mod;}for(int k=n-1;k>=0;k--){v[k]=(v[k]-v[k-1]+mod)%mod;ans=(ans+k*v[k]%mod)%mod;}ans=ans*ny[n]%mod;printf("%lld",ans);return 0;
}

这篇关于2023NOIP A层联测6 冒泡排序趟数期望的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---