题外话：好久没写blog了啊～～
题目大意：给你m条长度为ai的线段，求在其中任选三条出来，能构成三角形的概率。即求在这n条线段中找出三条线段所能拼出的三角形数量除以$\binom{m}{3}$。
假设我们手中有3条长度分别为$x,y,z$的边(为了简化问题我们假设$x<y<z$，$x,y,z$相等的情况另行讨论)，如果他们能拼成三角形，必然满足$x+y>z$且$z-y<x$。
该题的$O(m^3)$做法：枚举其中的3条边，套用上面的判断公式，进行累计。
但通过简单的变式，我们假设我们已经确定了$x$和$y$，那么$z$的范围即为$[y,x+y)$，我们维护一个数组$num$，$num_i$表示长度为i的线段数量。再维护一个num的前缀和sum。则$ans=\sum^{n-1}_{x=1} \sum^{n}_{y=x+1} num_x * num_y*(sum[x+y-1]-sum[y])$，运算该和式的时间复杂度为$O(n^2)$，此处的n表示最长线段的长度。
然而还是会TLE。。。。
我们考虑对其做一些变式。
$ans=\sum^{n-1}_{x=1} \sum^{n}_{y=x+1} num_x * num_y*(sum[x+y-1]-sum[y])$
$=\sum^{n-1}_{x=1} \sum^{n}_{y=x+1} num_x * num_y*sum[x+y-1] -\sum^{n-1}_{x=1} \sum^{n}_{y=x+1} num_x * num_y*sum[y]$
该式子的后半部分，我们可以通过维护$num_y*sum[y]$的后缀和，实现O(n)的计算。
下面我们继续对式子的前半部分变式。令t=x+y。则有
$=\frac{1}{2}\sum^{2n}_{t=2} \sum^{t-1}_{p=1} num_p*num_{t-p}*sum[t-1] -\frac{1}{2}\sum^{n}_{i=1}num_i^2*sum[2*i-1]$
我们发现，该式子的$\sum_{p=1}^{t-1} num_{p}\times num_{t-p}$，可以用FFT求出。则时间复杂度成功降低至O(n log n)，而式子的后半部分可以O(n)求出，求和时间复杂度降低至O(n log n)。
下面说下x=y=z，x=y<z，x<y=z的处理方法。
x=y=z:$\sum _{\forall num_x>2} \binom{num_x}{3}$
x=y<z: $\sum _{x=1}^{n} \binom{num_x}{2}*(sum[2x-1]-sum[x])$
x<y=z:$\sum_{x=1}^{n}(sumc2_n-sumc2_x)$ ，其中$sumc2_x$ 表示$\sum_{i=1}^{x}\binom{num_x}{2}$。
把这三种情况和最初描述的情况相加即可。
#include<bits/stdc++.h>
#define M 270000
#define cp complex<double>
#define PI acos(-1)
#define L long long
using namespace std;
cp a[M];
void change(cp a[],int len){
for(int i=,j=;i<len-;i++){
if(i<j) swap(a[i],a[j]);
int k=len>>;
while(j>=k) j-=k,k>>=;
j+=k;
}
}
void fft(cp a[],int n,int on){
change(a,n); cp t,u;
for(int h=;h<=n;h<<=){
cp wn(cos(-on**PI/h),sin(-on**PI/h));
for(int j=;j<n;j+=h){
cp w(,);
for(int k=j;k<j+(h>>);k++){
u=a[k]; t=w*a[k+(h>>)];
a[k]=u+t; a[k+(h>>)]=u-t;
w=w*wn;
}
}
}
}
L num[M]={},sum[M]={},sumhh[M]={},sumc2[M]={},sc[M]={},ans=; int Main(){
int m,n,maxn=; scanf("%d",&n);
for(int i=;i<=n;i++){
int x; scanf("%d",&x);
num[x]++; maxn=max(maxn,x);
}
for(m=;m<(maxn*+);m<<=);
for(int i=;i<m;i++) a[i]=cp(num[i],);
fft(a,m,);
for(int i=;i<m;i++) a[i]=a[i]*a[i];
fft(a,m,-);
for(int i=;i<m;i++) sc[i]=(a[i+].real()+0.5)/m;
for(int i=;i<m;i++){
sum[i]=sum[i-]+num[i];
sumc2[i]=sumc2[i-]+num[i]*(num[i]-)/;
} L ans1=,ans2=,ans3=,ans4=;
for(int i=;i<=maxn;i++) if(num[i]>)
ans1+=(L)num[i]*(num[i]-)*(num[i]-);
ans1/=;//x=y=z
for(int i=;i<=maxn;i++)
ans2+=(L)num[i]*(num[i]-)*(sum[*i-]-sum[i]);
ans2/=;//x=y<z
for(int i=;i<=maxn;i++)
ans3+=num[i]*(sumc2[maxn]-sumc2[i]);
//x<y=z
for(int i=;i<*maxn;i++) ans4+=sum[i]*sc[i];
for(int i=;i<=maxn;i++) ans4-=num[i]*num[i]*sum[*i-];
ans4/=;//x<y<z卷积部分 for(int i=maxn;i;i--) sumhh[i]=sumhh[i+]+num[i]*sum[i];
for(int i=;i<maxn;i++) ans4-=num[i]*sumhh[i+];
ans=ans1+ans2+ans3+ans4; double fenmu=(L)n*(n-)*(n-)/;
double hh=ans/fenmu;
printf("%.7lf\n",hh);
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int cas; scanf("%d",&cas);
while(cas--){
memset(num,,sizeof(num)); memset(sum,,sizeof(sum));
memset(sumhh,,sizeof(sumhh)); memset(sumc2,,sizeof(sumc2));
memset(sc,,sizeof(sc)); memset(a,,sizeof(a)); ans=;
Main();
}
}