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);
}
}
上一篇:Bigtable:一个分布式的结构化数据存储系统


下一篇:剑指Offer面试题:23.二叉树中和为某一值的路径