记录编号	457178	评测结果	AAAAAAAAAA
题目名称	[焦作一中2012] 概率游戏	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.072 s
提交时间	2017-10-06 21:42:14	内存使用	0.82 MiB

# include "algorithm"
# include "stdio.h"
# define maxn 100005
# define N 100000 
# define int long long
using namespace std;
int n,x,ai,s[maxn],sum[maxn*4],tot,f;
void update(int l,int r,int rt,int pos){
	 if(l==r) {sum[rt]++;return;}
     int mid=(l+r)>>1;
     if(mid>=pos) update(l,mid,rt*2,pos);
     if(mid<pos) update(mid+1,r,rt*2+1,pos);
     sum[rt]=sum[rt*2]+sum[rt*2+1];
}
int query(int l,int r,int rt,int L,int R){
	 if(L<=l&&R>=r) return sum[rt];
	 int mid=(l+r)>>1,ret=0;
	 if(L>mid) return query(mid+1,r,rt*2+1,L,R);	 
	 else if(R<=mid) return query(l,mid,rt*2,L,R);
	      else return query(mid+1,r,rt*2+1,L,R)+query(l,mid,rt*2,L,R);
}
int cpp(){
	freopen("probability.in","r",stdin);
	freopen("probability.out","w",stdout);
	scanf("%lld%lld",&n,&x);
	for(int i=1;i<=n;i++){
		scanf("%lld",&s[i]);
		update(1,100000,1,s[i]);
	}
	for(int i=1;i<=n;i++){
	    int t=x-s[i];
	    if(t<1) continue;
		tot+=query(1,100000,1,1,t);
		if(s[i]<=t) tot--;
	}f=n*(n-1)/2;
	tot/=2;
	double ans=(double) tot/f;
	printf("%.2lf",ans); 
}int start=cpp();
signed main(){;}