hdu 4609 3-idiots

http://acm.hdu.edu.cn/showproblem.php?pid=4609

FFT  不会 找了个模板

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long ll;
typedef pair<double,double>ppd;
const double PI = acos(-1.);
const int MAXL = (1 << 18)+100;
int a[MAXL],b[MAXL];
ll c[MAXL];
ppd A[MAXL],B[MAXL],C[MAXL],T[MAXL];
int id,ln;
void fill0(int m,int d,int *s,ppd *P)
{
    if (m == ln)
        P[d] = make_pair(s[id++],0.0);
    else
    {
        fill0(m<<1,d,s,P);
        fill0(m<<1,d+m,s,P);
    }
}

void fill1(int m,int d,ppd *C,ppd *P)
{
    if (m == ln) P[d] = C[id++];
    else
    {
        fill1(m<<1,d,C,P);
        fill1(m<<1,d+m,C,P);
    }
}

void fft(double oper,ppd *P)
{
    for (int d = 0;(1 << d) < ln;++d)
    {
        int m = (1 << d);
        double p0 = PI / m * oper;
        double sinp0 = sin(p0);
        double cosp0 = cos(p0);
        for (int i = 0;i < ln;i += (m << 1))
        {
            double sinp = 0;
            double cosp = 1;
            for (int j = 0;j < m;++j)
            {
                double ta = cosp * P[i+j+m].first - sinp*P[i+j+m].second;
                double tb = cosp * P[i+j+m].second + sinp * P[i+j+m].first;
                P[i+j+m].first = P[i+j].first - ta;
                P[i+j+m].second = P[i+j].second - tb;
                P[i+j].first += ta;
                P[i+j].second += tb;
                double tsinp = sinp;
                sinp = sinp * cosp0 + cosp * sinp0;
                cosp = cosp * cosp0 -tsinp * sinp0;
            }
        }
    }
}
void polyMul(int *a,int *b,ll *c,int n)
{
    ln=(1<<18);
    while((ln>>2)>=n) ln=ln>>1;
    id = 0;
    fill0(1,0,a,A);
    fft(1.0,A);
    id = 0;
    fill0(1,0,b,B);
    fft(1.0,B);
    for (int i = 0;i < ln;++i)
    {
        C[i].first = A[i].first * B[i].first - A[i].second * B[i].second;
        C[i].second = A[i].first * B[i].second + A[i].second * B[i].first;
    }
    id = 0;
    fill1(1,0,C,T);
    fft(-1.0,T);
    for (int i = 0;i < ln;++i)
        c[i] = ll(T[i].first / ln + 0.1);
}
int main()
{
    //freopen("data.in","r",stdin);
    //freopen("1010.in","r",stdin);
    //freopen("my.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int m;
        scanf("%d",&m);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        int n=0;
        for(int i=0;i<m;++i)
        {
            int tmp=0;
            scanf("%d",&tmp);
            n=max(n,tmp);
            ++a[tmp];
            ++b[tmp];
        }
        ++n;
        polyMul(a,b,c,n);
        for(int i=0;i<n;++i)
        if(a[i])
        c[i+i]-=a[i];
        for(int i=0;i<ln;++i)
        c[i]=c[i]>>1;

        double tmp=0.0;
        double t=0;
        for(int i=0;i<n;++i)
        {
            t+=c[i];
            tmp+=(a[i]*t);
        }
        double sum=(1.0*m*(m-1)*(m-2)/2/3);
        printf("%.7lf
",(sum-tmp)/sum);
    }
    return 0;
}