HDU 4709 3-idiots FFT 多项式

时间：2024-01-21 18:29:51

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

给一堆边，求这一堆边随便挑三个能组成三角形的概率。

裸fft，被垃圾题解坑了还以为很难。

最长的边的长度小于其余两边之和是组成三角形的充要条件，fft搞搞就行了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<complex>

 using namespace std;

 #define LL long long

 const int maxn=;

 double Pi;

 typedef complex< double >cd;

 cd b[maxn]={};

 LL a[maxn]={},cnt[maxn]={};

 int bel[maxn]={},s,bt;

 void getit(){for(int i=;i<s;++i)bel[i]=(bel[i>>]>>)|((i&)<<(bt-));}

 void fft(cd *c,int n,int dft){

     for(int i=;i<n;++i)if(bel[i]>i)swap(c[i],c[bel[i]]);

     for(int step=;step<n;step<<=){

         cd w=cd(cos(Pi/(double)step),sin(Pi/(double)step)*(double)dft);

         for(int j=;j<n;j+=(step<<)){

             cd z=cd(1.0,);

             for(int i=j;i<j+step;++i){

                 cd x=c[i],y=c[i+step]*z;

                 c[i]=x+y;c[i+step]=x-y;

                 z=z*w;

             }

         }

     }

     if(dft==-)for(int i=;i<n;++i)c[i]/=n;

 }

 int main(){

     Pi=acos(-1.0);

     int T;scanf("%d",&T);

     while(T-->){

         int n;scanf("%d",&n);

         memset(cnt,,sizeof(cnt));

         for(int i=;i<n;++i){scanf("%d",&a[i]);cnt[a[i]]+=;}

         sort(a,a+n); int siz=a[n-]+;

         for(int i=;i<siz;++i)b[i]=cd(cnt[i],);

         for(int i=siz;i<s;++i)b[i]=cd(,);

         siz*=; bt=; s=; for(;s<siz;++bt)s<<=; getit();

         fft(b,s,);

         for(int i=;i<s;++i)b[i]=b[i]*b[i];

         fft(b,s,-);

         for(int i=;i<=s;++i)cnt[i]=(LL)(b[i].real()+0.5);

         for(int i=;i<s;++i)b[i]=cd(,);

         s=a[n-]*;

         for(int i=;i<n;++i)--cnt[a[i]*];

         for(int i=;i<=s;++i)cnt[i]/=;

         for(int i=;i<=s;++i)cnt[i]+=cnt[i-];

         LL ans=;

         for(int i=;i<n;++i){

             ans+=cnt[s]-cnt[a[i]];

             ans-=(LL)(n--i)*i;

             ans-=n-;

             ans-=(LL)(n--i)*(n-i-)/;

         }

         LL sum=(LL)n*(n-)*(n-)/;

         printf("%.7f\n",(double)(ans)/(double)(sum));

     }

     return ;

 }

相关文章