[原创]hdu 4609 3-idiots [FFT计数]【数学】

# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
# define no         puts("NO")

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int    MOD = 1e9+7;
const int    N   = 264000+5;
const double eps = 1e-6;
const double PI  = acos(-1.0);
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}

/***********************************************************************/
struct Complex{
    double real, image;
    Complex(double _real, double _image){
        real = _real;
        image = _image;
    }
    Complex(){}

    Complex operator + (const Complex &tmp){
        return Complex(real + tmp.real, image + tmp.image);
    }
    Complex operator - (const Complex &tmp){
        return Complex(real - tmp.real, image - tmp.image);
    }
    Complex operator * (const Complex &tmp){
        return Complex(real*tmp.real - image*tmp.image, real*tmp.image + image*tmp.real);
    }
};
int rev(int id, int len){
    int ret = 0;
    for(int i = 0; (1 << i) < len; i++){
        ret <<= 1;
        if(id & (1 << i)) ret |= 1;
    }
    return ret;
}
Complex A[264000];
void FFT(Complex *a, int len, int DFT){
    for(int i = 0; i < len; i++)
        A[rev(i, len)] = a[i];
    for(int s = 1; (1 << s) <= len; s++){
        int m = (1 << s);
        Complex wm = Complex(cos(DFT*2*PI/m), sin(DFT*2*PI/m));
        for(int k = 0; k < len; k += m){
            Complex w = Complex(1, 0);
            for(int j = 0; j < (m >> 1); j++){
                Complex t = w*A[k + j + (m >> 1)];
                Complex u = A[k + j];
                A[k + j] = u + t;
                A[k + j + (m >> 1)] = u - t;
                w = w*wm;
            }
        }
    }
    if(DFT == -1) for(int i = 0; i < len; i++) A[i].real /= len, A[i].image /= len;
    for(int i = 0; i < len; i++) a[i] = A[i];
    return;
}


int num[100010]，h[200010];
Complex a[264000];
LL tA[200010]，sum[200010];

int main()
{
    int _, n;
    while(~scanf("%d", &_))
    while(_--)
    {
        scanf("%d", &n);
        int mx = 0;
        memset(h, 0, sizeof(h));
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &num[i]);
            h[num[i]]++;
        }
        sort(num+1, num + n+1);
        mx = num[n];

        int len = 1;
        while(len <= mx) len <<= 1;  len <<= 1;
        for(int i = 0; i < len; i++)  a[i] = Complex((i<=mx)?h[i]:0, 0);

        FFT(a, len, 1);
        for(int i = 0; i < len; i++)   a[i] = a[i]*a[i];
        FFT(a, len, -1);
        for(int i = 0; i <= (mx<<1); i++)   tA[i] = (LL)(a[i].real + 0.5);

        for(int i=0;i<=n;i++) tA[num[i]<<1]--;
        for(int i = 0; i <= (mx<<1); i++)  tA[i] >>=1;
        //到现在为止A[i]表示的是去两根不同的branch的长度和为i的组合种数
        sum[0] = 0;
        for(int i = 1; i <= (mx<<1); i++)  sum[i] = sum[i - 1] + tA[i];
        LL ans = 0;

        for(int i = 1; i <= n; i++)//以第i根作为边最长的
        {
            LL tmp = sum[(mx<<1)] - sum[num[i]];//另外两条边长度和要大于branch[i]
            tmp -= (LL)(n - i)*(i - 1);//另外两条一条比branch[i]长, 一条不比它长
            tmp -= (LL)(n - i)*(n - i - 1) / 2;//两条都比他长
            tmp -= n - 1;//另外两条的组合中包括它自己的组合
            ans += tmp;
        }
        printf("%.7f\n",ans*6./n/(n - 1)/(n - 2));
    }
    return 0;
}