开发笔记:HDU47093idiotsFFT多项式

1 #include<iostream>
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8 #define LL long long
9 const int maxn=530010;
10 double Pi;
11 typedef complex<double >cd;
12 cd b[maxn]={};
13 LL a[maxn]={},cnt[maxn]={};
14 int bel[maxn]={},s,bt;
15 void getit(){for(int i=0;i>1]>>1)|((i&1)<<(bt-1));}
16 void fft(cd *c,int n,int dft){
17 for(int i=0;iif(bel[i]>i)swap(c[i],c[bel[i]]);
18 for(int step=1;step1){
19 cd w=cd(cos(Pi/(double)step),sin(Pi/(double)step)*(double)dft);
20 for(int j=0;j1)){
21 cd z=cd(1.0,0);
22 for(int i=j;ii){
23 cd x=c[i],y=c[i+step]*z;
24 c[i]=x+y;c[i+step]=x-y;
25 z=z*w;
26 }
27 }
28 }
29 if(dft==-1)for(int i=0;in;
30 }
31 int main(){
32 Pi=acos(-1.0);
33 int T;scanf("%d",&T);
34 while(T-->0){
35 int n;scanf("%d",&n);
36 memset(cnt,0,sizeof(cnt));
37 for(int i=0;i"%d",&a[i]);cnt[a[i]]+=1;}
38
39 sort(a,a+n); int siz=a[n-1]+1;
40 for(int i=0;i0);
41 for(int i=siz;i0,0);
42
43 siz*=2; bt=1; s=2; for(;s1; getit();
44 fft(b,s,1);
45 for(int i=0;ib[i];
46 fft(b,s,-1);
47 for(int i=0;i<=s;++i)cnt[i]=(LL)(b[i].real()+0.5);
48 for(int i=0;i0,0);
49
50 s=a[n-1]*2;
51 for(int i=0;i2];
52 for(int i=1;i<=s;++i)cnt[i]/=2;
53 for(int i=1;i<=s;++i)cnt[i]+=cnt[i-1];
54
55 LL ans=0;
56 for(int i=0;ii){
57 ans+=cnt[s]-cnt[a[i]];
58 ans-=(LL)(n-1-i)*i;
59 ans-=n-1;
60 ans-=(LL)(n-1-i)*(n-i-2)/2;
61 }
62 LL sum=(LL)n*(n-1)*(n-2)/6;
63 printf("%.7f
",(double)(ans)/(double)(sum));
64 }
65 return 0;
66 }