【FFT】HDU4609-3 idiots

..退化为一天两题了，药丸..

【题目大意】

给出n根木棍的长度，求从其中取出3根能组成三角形的概率。

【思路】

然后枚举求前缀和，枚举最长边。假设最长边为l，先求出所有两边之和大于它的情况数。然后减去两边都大于它的情况以及一大一小的情况。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<complex>

 #include<cmath>

 #define pi acos(-1)

 using namespace std;

 const int MAXN = ;

 typedef complex<double> com;

 typedef long long ll;

 int n,m,L,tmpn;

 com a[MAXN],b[MAXN];

 int c[MAXN],Rev[MAXN],l[MAXN],len;

 ll sum[MAXN],num[MAXN];//把sum和num放在子程序里就会错误，放进主程序就可以，为什么？？

 void get_bit(){for (n=,L=;n<m;n<<=) L++;}

 void get_Rtable(){for (int i=;i<n;i++) Rev[i]=(Rev[i>>]>>)|((i&)<<(L-));}

 void multi(com* a,com* b){for (int i=;i<n;i++) a[i]*=b[i];}

 void FFT(com* a,int flag)

 {

     for (int i=;i<n;i++)if(i<Rev[i])swap(a[i],a[Rev[i]]); //利用逆序表，快速求逆序

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

     {

         com wn(cos(*pi/(i*)),flag*sin(*pi/(i*)));

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

         {

             com w(,);

             for (int k=;k<i;k++,w*=wn)

             {

                 com x=a[j+k],y=w*a[j+k+i];

                 a[j+k]=x+y;

                 a[j+k+i]=x-y;

             }

         }

     }

     if (flag==-) for (int i=;i<n;i++) a[i]/=n;

 }

 void init()

 {

     int tmp[MAXN/];

     scanf("%d",&n);

     tmpn=n;

     memset(tmp,,sizeof(tmp));

     memset(Rev,,sizeof(Rev));

     len=-;

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

     {

         scanf("%d",&l[i]);

         if (len<l[i]) len=l[i];

         tmp[l[i]]++;

     }

     for (int i=;i<MAXN;i++) a[i]=b[i]=();

     for (int i=;i<=len;i++) a[i]=(tmp[i]);

 }

 void solve()

 {

     m=len<<;

     len++;m++;

     get_bit();

     get_Rtable();

     FFT(a,);

     for (int i=;i<n;i++) b[i]=a[i];

     multi(a,b);

     FFT(a,-);

 }

 void get_ans()

 {

     memset(sum,,sizeof(sum));

     memset(num,,sizeof(num));

     for (int i=;i<m;i++) num[i]=(ll)(a[i].real()+0.5);

     //减掉取两个相同的组合

     for(int i =;i<tmpn;i++)

     {

         num[l[i]+l[i]]--;

     }

     for (int i=;i<m;i++) num[i]/=;

     sum[]=;

     for (int i=;i<m;i++) sum[i]=sum[i-]+num[i];

     ll cnt=;

     n=tmpn;

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

     {

         cnt+=sum[m-]-sum[l[i]];

         //减掉一个取大，一个取小的

         cnt-= (ll)(n--i)*i;

         //减掉一个取本身，另外一个取其它

         cnt-= (n-);

         //减掉大于它的取两个的组合

         cnt-= (ll)(n--i)*(n-i-)/;

     }

     ll tot = (ll)n*(n-)*(n-)/;

     printf("%.7lf\n",(double)cnt/tot);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while (T--)

     {

         init();

            solve();

         get_ans();

     }

     return ;

 }