[HDU4609] 3-idiots FFT+计数

用FFT再去重计算出两条边加起来为某个值得方案数,然后用总方案数减去不合法方案数即可.

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<ctime>

#include<string>

#include<iomanip>

#include<algorithm>

#include<map>

using namespace std;

#define LL long long

#define FILE "dealing"

#define up(i,j,n) for(LL i=j;i<=n;++i)

#define db double

#define ull unsigned long long

#define eps 1e-10

#define pii pair<LL,LL>

LL read(){

	LL x=0,f=1,ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f*x;

}

const LL maxn=402000,maxm=20000,mod=(LL)(1e9+7+0.1),limit=(LL)(1e6+1),inf=(LL)(1e9);

bool cmax(LL& a,LL b){return a<b?a=b,true:false;}

bool cmin(LL& a,LL b){return a>b?a=b,true:false;}

namespace FFT{

	db pi=acos(-1.0);

	struct cp{

		db x,y;

		cp(db x=0,db y=0):x(x),y(y){}

		cp operator+(const cp& b){return cp(x+b.x,y+b.y);}

		cp operator-(const cp& b){return cp(x-b.x,y-b.y);}

		cp operator*(const cp& b){return cp(x*b.x-y*b.y,x*b.y+y*b.x);}

	}w[maxn],a[maxn],b[maxn];

	LL R[maxn],H,L;

	void FFT(cp* a,LL f){

		up(i,0,L-1)if(i<R[i])swap(a[i],a[R[i]]);

		for(LL len=2;len<=L;len<<=1){

			LL l=len>>1;

			cp wn(cos(pi/l),f*sin(pi/l));

			up(i,1,l-1)w[i]=w[i-1]*wn;

			for(LL st=0;st<L;st+=len)

				for(LL k=0;k<l;k++){

					cp x=a[st+k],y=w[k]*a[st+k+l];

					a[st+k]=x+y;a[st+k+l]=x-y;

				}

		}

		if(f==-1)up(i,0,L-1)a[i].x/=L;

	}

	void solve(LL* c,LL* d,LL n,LL m,LL* ch){

		n++,m++;

		up(i,0,n-1)a[i].x=c[i],a[i].y=0;

		up(i,0,m-1)b[i].x=d[i],b[i].y=0;

		for(H=0,L=1;L<n+m-1;H++)L<<=1;

		up(i,n,L)a[i].x=a[i].y=b[i].x=b[i].y=0;

		up(i,1,L)R[i]=(R[i>>1]>>1)|((i&1)<<(H-1));

		w[0].x=1;

		FFT(a,1);FFT(b,1);

		up(i,0,L-1)a[i]=a[i]*b[i];

		FFT(a,-1);

		up(i,1,n+m-1)ch[i]=(LL)(a[i].x+0.5);

	}

};

LL n,m;

LL a[maxn],b[maxn],c[maxn],v[maxn],Max=0,sum=0;

db ans=0;

int main(){

	freopen(FILE".in","r",stdin);

	freopen(FILE".out","w",stdout);

	LL T=read();

	while(T--){

		memset(v,0,sizeof(v));

		memset(b,0,sizeof(b));

		n=read();

		Max=0;sum=0;

		up(i,1,n)v[(a[i]=read())]++,cmax(Max,a[i]);

		FFT::solve(v,v,Max,Max,b);

		up(i,1,n)b[a[i]<<1]--;

		up(i,1,Max<<1)b[i]>>=1;

		for(LL i=Max;i>=1;i--)v[i]+=v[i+1];

		for(LL i=Max;i>=1;i--)sum+=b[i]*v[i];

		LL S=(LL)n*(n-1)*(n-2)/6;

		ans=(S-sum*1.0)/S;

		printf("%.7lf\n",ans);

	}

	return 0;

}