HDU4609 & FFT

关于这道题请移步kuangbin爷的blog:http://www.cnblogs.com/kuangbin/archive/2013/07/24/3210565.html

感觉我一辈子也不能写出这么详细的题解.

Code:

　　

/*=================================

# Created time: 2016-04-18 16:03

# Filename: hdu4609.cpp

# Description:

=================================*/

#define me AcrossTheSky&HalfSummer11

#include <cstdio>

#include <cmath>

#include <ctime>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <set>

#include <stack>

#include <queue>

#include <vector>

#define lowbit(x) (x)&(-x)

#define Abs(x) ((x) > 0 ? (x) : (-(x)))

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define getlc(a) ch[(a)][0]

#define getrc(a) ch[(a)][1]

#define maxn 300005

#define maxm 100005

#define INF 1070000000

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

template<class T> inline

void read(T& num){

    num = 0; bool f = true;char ch = getchar();

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

    while(ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';ch = getchar();}

    num = f ? num: -num;

}

int outs[100];

template<class T> inline

void write(T x){

	if (x==0) {putchar('0'); putchar(' '); return;}

	if (x<0) {putchar('-'); x=-x;}

	int num=0;

	while (x){ outs[num++]=(x%10); x=x/10;}

	FORM(i,num-1,0) putchar(outs[i]+'0'); putchar(' ');

}

/*==================split line==================*/

const double pi=acos(-1);

struct cpx{

	double x,y;

	cpx(double a=0,double b=0):x(a),y(b){}

}f[maxn],g[maxn],eps[maxn],inv_eps[maxn];

	inline cpx operator +(cpx a,cpx b){return cpx(a.x+b.x,a.y+b.y);}

	inline cpx operator -(cpx a,cpx b){return cpx(a.x-b.x,a.y-b.y);}

	inline cpx operator *(cpx a,cpx b){return cpx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

	inline cpx conj(cpx a){return cpx(a.x,-a.y);}

inline void geteps(ll n){

	double angle=2*pi/n;

	FORP(i,0,n) { double t=angle*i; eps[i]=cpx(cos(t),sin(t)); inv_eps[i]=conj(eps[i]);}

}

inline void fft(ll n,cpx *buffer,cpx *eps){

	for (ll i=0,j=0;i<n;i++){

		if (i<j) swap(buffer[i],buffer[j]);

		for (ll l=n>>1;(j^=l)<l;l>>=1);

	}

	for (ll i=2;i<=n;i<<=1){

		ll m=i>>1;

		for (ll j=0;j<n;j+=i)

			for (ll k=0;k<m;k++){

				cpx z=buffer[j+m+k]*eps[n/i*k];

				buffer[j+m+k]=buffer[j+k]-z;

				buffer[j+k]=buffer[j+k]+z;

			}

	}

}

ll a[100005],num[maxn];

int main(){

	int cas; read(cas);

	while (cas--){

		//f.clear(); g.clear();

		memset(f,0,sizeof(f)); //memset(g,0,sizeof(g));

		int n; read(n);

		ll maxa=0;

		FORP(i,1,n) {read(a[i]); maxa=max(maxa,a[i]); f[a[i]].x++;} //g[a[i]]=f[a[i]];}

		ll k=1;

		while(k<=maxa) k<<=1;

		k<<=1;

		geteps(k);

		fft(k,f,eps); //fft(k,g,eps);

		FORP(i,0,k-1) f[i]=f[i]*f[i];

		fft(k,f,inv_eps);

		FORP(i,0,k-1) f[i].x/=(double)k;

		//memset(num,0,sizeof(num));

		FORP(i,0,k-1) num[i]=trunc(f[i].x+0.5);

		FORP(i,1,k-1) if (num[i]<0) printf("flag\n");

		FORP(i,1,n) num[a[i]+a[i]]--;

		FORP(i,0,k-1) num[i]/=2;

		FORP(i,1,k-1) num[i]+=num[i-1];

		sort(a+1,a+1+n);

		ll ans=0;

		for(ll i=1;i<=n;i++)

			ans=ans+num[k-1]-num[a[i]]-(n-1)-(i-1)*(n-i)-(n-i)*(n-i-1)/2;

		ll down=(ll)n*(n-1)*(n-2)/6;

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

	}

}