HDU46093-idiots

题目大意

给一堆边的长度，问从中随机选出三条边来能够组成三角形的概率。

题解

其实就是要求能够组成三角形的方案数。
直接从三条边入手问题会很复杂，所以我们可以先求出f[x]表示随便选出两条边长度之和为x的方案数。

这个数组用FFT+乱搞一下就可以求出来。

然后考虑枚举最长边，那么剩下两条边之和显然要大于这条边，但我们还要减掉自己本身和其他边配对的方案数，比这条边小的边和比它大的边匹配的方案数，比它大的边和比它大的边配对的方案。

注意下细节就好了，记得中间转longlong不要写int。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<ctime>
#define N 800009
using namespace std;
const int maxn=100000;
typedef long long ll;
const double pai=acos(-1.0);
int rev[N],l,L,ma,n,t,a[N];
ll ans,num[N];
inline int rd(){
    int x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
struct fs{
    double x,y;
    fs(){x=y=0;}
    fs(double xx,double yy){x=xx;y=yy;}
    fs operator +(const fs &b)const{return fs{x+b.x,y+b.y};}
    fs operator -(const fs &b)const{return fs{x-b.x,y-b.y};}
    fs operator *(const fs &b)const{return fs{x*b.x-y*b.y,x*b.y+y*b.x};}
}c[N];
void FFT(fs *a,int tag){
    for(int i=0;i<l;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
    for(int j=1;j<l;j<<=1){
        fs wn(cos(pai/j),tag*sin(pai/j));
        for(int k=0;k<l;k+=(j<<1)){
            fs w(1,0);
            for(int i=0;i<j;i++,w=w*wn){
                fs xx=a[k+i],yy=w*a[k+j+i];
                a[k+i]=xx+yy;a[k+j+i]=xx-yy; 
            }
        }
    }
}
inline void init(){
    ma=ans=0;
    memset(num,0,sizeof(num));
}
int main(){
//    freopen("in","r",stdin);
//    freopen("out1","w",stdout);
    t=rd();
    while(t--){
        n=rd();init();
        for(int i=1;i<=n;++i){
          a[i]=rd(),c[a[i]].x++;ma=max(ma,a[i]);
        }
        l=1;L=0;
        while(l<=(ma<<1))l<<=1,L++;
        for(int i=1;i<l;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
        FFT(c,1);
        for(int i=0;i<l;++i)c[i]=c[i]*c[i];
        FFT(c,-1);
        for(int i=0;i<l;++i)c[i].x=(long long)(c[i].x/l+0.5);
        for(int i=1;i<=n;++i)c[a[i]*2].x--;
        for(int i=0;i<l;++i)num[i]=(c[i].x)/2;sort(a+1,a+n+1);
        for(int i=1;i<l;++i)num[i]+=num[i-1];
        for(int i=1;i<=n;++i){
            ll nu=num[l-1]-num[a[i]];
            nu-=1ll*(n-1);
            nu-=1ll*(n-i-1)*(n-i)/2;
            nu-=1ll*(i-1)*(n-i);
            ans+=nu;
        }
        for(int i=0;i<l;++i)c[i].x=c[i].y=0;
        printf("%.7lf
",(double)ans*1.0/((double)n*(n-1)*(n-2)/6));
    }
    return 0;
}