正难则反，首先概率就是\(\frac{合法的方案数}{总的方案数}\)=\(\frac{总的方案数-不合法的方案数}{总的方案数}\)，统计不合法的方案数只需要 两个较短的边的长度和\(\le\)较长的边，用t[i]表示长度大于等于i的木棍的数量，f[i]为长度为i的木棍的数量,g[i]表示选出两根木棍组成和为i的方案数,很明显g等于f卷上f，注意自己不能卷自己，直接在最后让自己卷自己的方案数减去就行了。然后\(\displaystyle \sum \frac{g[i]}{2} \times t[i]\)就是不合法的方案数了。
bzoj数据比较毒瘤，NTT超时了，得用FFT才能过…
#include<bits/stdc++.h>
#define DB double
#define LL long long
#define AK 0
#define IOI ;
using namespace std;
int T,n,x,maxx,lim;
LL ans,tot;
const int N=400010;
const DB PI=acos(-1);
int r[N],t[N];
LL g[N];//f3?ê?·?°? gá??ùD???1÷μ?·?°? tò??ù′óóúμèóúiμ?·?°?
inline int read()
{
int res = 0; char ch = getchar(); bool XX = false;
for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
return XX ? -res : res;
}
struct xu
{
DB x,y;
xu(DB X=0,DB Y=0){x=X,y=Y;}
friend xu operator +(const xu &a,const xu &b)
{return (xu){a.x+b.x,a.y+b.y};}
friend xu operator -(const xu &a,const xu &b)
{return (xu){a.x-b.x,a.y-b.y};}
friend xu operator *(const xu &a,const xu &b)
{return (xu){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
}f[N];
void FFT(xu *A,int lim,int opt)
{
for(int i=0;i<lim;++i)
r[i]=(r[i>>1]>>1)|((i&1)?(lim>>1):0);
for(int i=0;i<lim;++i)
if(i<r[i])swap(A[i],A[r[i]]);
int len;
xu wn,w,x,y;
for(int mid=1;mid<lim;mid<<=1)
{
len=mid<<1;
wn=(xu){cos(PI/mid),opt*sin(PI/mid)};
for(int j=0;j<lim;j+=len)
{
w=(xu){1,0};
for(int k=j;k<j+mid;++k,w=w*wn)
{
x=A[k];y=A[k+mid]*w;
A[k]=x+y; A[k+mid]=x-y;
}
}
}
}
void YYch()
{
for(int i=0;i<=lim;++i)f[i]=g[i]=t[i]=0;
maxx=0;lim=1;ans=tot=0;
}
inline void treAKer()
{
YYch();
cin>>n;
for(int i=1;i<=n;++i)
{
maxx=max(maxx,x=read());
f[x].x++;t[x]++;g[x<<1]--;
}
for(int i=maxx;i>=1;--i)t[i]+=t[i+1];
while(lim<=(maxx<<1))lim<<=1;
FFT(f,lim,1);
for(int i=0;i<lim;++i)f[i]=f[i]*f[i];
FFT(f,lim,-1);
for(int i=0;i<lim;++i)g[i]+=(int)(f[i].x/lim+0.5);
tot=(LL)n*(n-1)*(n-2)/6;
for(int i=0;i<lim;++i)ans+=(g[i]>>1)*t[i];
printf("%.7f\n",(double)(tot-ans)/tot);
}
int main()
{
cin>>T;
while(T--)treAKer();
return AK IOI;
}