首页 > 代码库 > 【codeforces 749E】 Inversions After Shuffle
【codeforces 749E】 Inversions After Shuffle
http://codeforces.com/problemset/problem/749/E (题目链接)
题意
给出一个1~n的排列,从中等概率的选取一个连续段,设其长度为l。对连续段重新进行等概率的全排列,求排列后整个原序列的逆序对的期望个数。
Solution
考虑对于每一对数${(a_i,a_j),i<j}$算贡献。
1.连续段包含${a_i,a_j}$
不妨设${a_i<a_j}$,则只有当排列后${a_j}$再${a_i}$前面才会对答案有贡献(${a_i>a_j}$的情况同理),连续段长度为${l}$。
于是满足${a_i}$在${a_j}$前面的排列数为${P_l^{l-2}}$,概率:${\frac{P_l^{l-2}}{P_l^l}=\frac{1}{2}}$。
满足包含${a_i}$和${a_j}$的连续段有${i*(n-j+1)}$个,其概率为:${\frac{2*i*(n-j+1)}{n*(n+1)}}$。
所以其期望等于两个概率相乘:
$${q_{i,j}=\frac{i*(n-j+1)}{n*(n+1)}}$$
这是${O(n^2)}$的,考虑优化。总期望:
$${Q=\sum_{i=1}^n \sum_{j=i+1}^n q_{i,j}}$$
$${Q=\sum_{i=1}^n \sum_{j=i+1}^n \frac{i*(n-j+1)}{n*(n+1)}}$$
发现${(n-j+1)}$是连续的,于是就变成了:
$${Q=\sum_{i=1}^n \frac {i*(n-i)*(n-i+1)} {2*n*(n+1)}}$$
这样复杂度就是${O(n)}$的了。
2.连续段不同时包含${a_i,a_j}$
如果${a_i<a_j}$,那么因为不被连续段同时包含,它们不会有机会改变相对位置,所以不会对答案做出贡献。考虑${a_i>a_j}$的情况。
那么连续段可能取到的区间有:${[1,j-1],[i+1,n]}$。考虑到区间${[i+1,j-1]}$被算了2次,容斥一下,所以区间的概率:
$${P=\frac {(j-1)*j+(n-i)*(n-i+1)-(j-i-1)*(i-j)} {n*(n+1)}}$$
然后好像用树状数组可以做,先坑着。。发个${O(n^2)}$的代码。
细节
代码
// codeforces 749E#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100010;LL c[maxn],s[maxn];int n,a[maxn];double ans;int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) ans+=(double)(i*(n-i)*(n-i+1))/(2*n*(n+1)); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (a[i]>a[j]) ans+=(double)((j-1)*j+(n-i)*(n-i+1)-(j-i-1)*(j-i))/(n*(n+1)); printf("%.12lf",ans); return 0;}
【codeforces 749E】 Inversions After Shuffle