题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4609
题意：给出n个正整数（数组A）。每次随机选出三个数。问这三个数能组成三角形的概率为多大？
思路：求出有多少种选择的方案，除以总选择方案即可。用num[i]表示长度为i的出现几次。
对于样例1 3 3 4,我们得到num={0,1,0,2,1}，
对num求卷积，得到：num={0,0,1,0,4,2,4,4,1}。此时的num[i]表示选择两个数和为i的选择方案的种数。 但是这里有重复的：
（1）两次不能选同一个数，这种情况要删去；
（2）对于两个数x和y，先选x后选y和先选y后选x，所以多算了一倍。
减去上面两种重复之后，我们得到：num={0,0,0,0,2,1,1,2}。接着设sum[i]为num的前缀和。接着将给出的数组A排序，开始统计答案。对于A[i]我们认为三个数中它是最大的，因此我们要选出在i之前的两个数使得其和大于A[i]，首先大于A[i]的情况有sum[Maxlen]-sum[A[i]]，然后要减去重的：
（1）一个选了i后面的一个选了i前面的；
（2）一个选了i另一个随便；
（3）两个都是i后面的。
struct node
{
double x,y;
node(double _x=0.0,double _y=0.0)
{
x=_x;
y=_y;
}
node operator+(node a)
{
return node(x+a.x,y+a.y);
}
node operator-(node a)
{
return node(x-a.x,y-a.y);
}
node operator*(node a)
{
return node(x*a.x-y*a.y,x*a.y+y*a.x);
}
};
node A[N];
int L;
int reverse(int x)
{
int ans=0,i;
FOR0(i,L) if(x&(1<<i)) ans|=1<<(L-1-i);
return ans;
}
void bitReverseCopy(node a[],int n)
{
int i;
FOR0(i,n) A[i]=a[i];
FOR0(i,n)
{
a[reverse(i)]=A[i];
}
}
void fft(node a[],int n,int on)
{
bitReverseCopy(a,n);
int len,i,j,k;
node x,y,u,t;
for(len=2;len<=n;len<<=1)
{
x=node(cos(-on*2*PI/len),sin(-on*2*PI/len));
for(j=0;j<n;j+=len)
{
y=node(1,0);
for(k=j;k<j+len/2;k++)
{
u=a[k];
t=y*a[k+len/2];
a[k]=u+t;
a[k+len/2]=u-t;
y=y*x;
}
}
}
if(on==-1)
{
FOR0(i,n) a[i].x/=n;
}
}
node a[N];
int d[N],n,m;
i64 num[N],sum[N];
int main()
{
rush()
{
RD(n);
clr(num,0);
int i;
FOR0(i,n) RD(d[i]),num[d[i]]++;
sort(d,d+n);
int len=d[n-1]+1;
m=1; L=0;
while(m<2*len) m<<=1,L++;
FOR0(i,len) a[i]=node(num[i],0);
for(i=len;i<m;i++) a[i]=node(0,0);
fft(a,m,1);
FOR0(i,m) a[i]=a[i]*a[i];
fft(a,m,-1);
FOR0(i,m) num[i]=(i64)(a[i].x+0.5);
m=d[n-1]<<1;
FOR0(i,n) num[d[i]<<1]--;
FOR1(i,m) num[i]>>=1,sum[i]=sum[i-1]+num[i];
i64 ans=0;
FOR0(i,n)
{
ans+=sum[m]-sum[d[i]];
ans-=(i64)i*(n-i-1);
ans-=n-1;
ans-=(i64)(n-1-i)*(n-2-i)/2;
}
i64 Sum=(i64)n*(n-1)*(n-2)/6;
PR(1.0*ans/Sum);
}
}