【FFT】HDU4609-3 idiots

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

【题目大意】

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

【思路】

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

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<complex>
  6 #include<cmath>
  7 #define pi acos(-1)
  8 using namespace std;
  9 const int MAXN = 400040;
 10 typedef complex<double> com;
 11 typedef long long ll;
 12 int n,m,L,tmpn;
 13 com a[MAXN],b[MAXN];
 14 int c[MAXN],Rev[MAXN],l[MAXN],len; 
 15 ll sum[MAXN],num[MAXN];//把sum和num放在子程序里就会错误，放进主程序就可以，为什么？？ 
 16 
 17 void get_bit(){for (n=1,L=0;n<m;n<<=1) L++;} 
 18 void get_Rtable(){for (int i=0;i<n;i++) Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(L-1));}
 19 void multi(com* a,com* b){for (int i=0;i<n;i++) a[i]*=b[i];}
 20 
 21 void FFT(com* a,int flag)
 22 {
 23     for (int i=0;i<n;i++)if(i<Rev[i])swap(a[i],a[Rev[i]]); //利用逆序表，快速求逆序
 24     for (int i=1;i<n;i<<=1)
 25     {
 26         com wn(cos(2*pi/(i*2)),flag*sin(2*pi/(i*2)));
 27         for (int j=0;j<n;j+=(i<<1))
 28         {
 29             com w(1,0);
 30             for (int k=0;k<i;k++,w*=wn)
 31             {
 32                 com x=a[j+k],y=w*a[j+k+i];
 33                 a[j+k]=x+y;
 34                 a[j+k+i]=x-y;
 35             }
 36         }
 37     }
 38     if (flag==-1) for (int i=0;i<n;i++) a[i]/=n;
 39 }
 40 
 41 void init()
 42 {
 43     int tmp[MAXN/4];
 44     scanf("%d",&n);
 45     tmpn=n;
 46     memset(tmp,0,sizeof(tmp));
 47     memset(Rev,0,sizeof(Rev));
 48     len=-1;
 49     for (int i=0;i<n;i++)
 50     {
 51         scanf("%d",&l[i]);
 52         if (len<l[i]) len=l[i];
 53         tmp[l[i]]++;
 54     } 
 55     for (int i=0;i<MAXN;i++) a[i]=b[i]=(0);
 56     for (int i=1;i<=len;i++) a[i]=(tmp[i]);
 57 }
 58 
 59 void solve()
 60 {
 61     m=len<<1;
 62     len++;m++;
 63     get_bit();
 64     get_Rtable();
 65     FFT(a,1);
 66     for (int i=0;i<n;i++) b[i]=a[i];
 67     multi(a,b);
 68     FFT(a,-1);
 69 }
 70 
 71 void get_ans()
 72 {    
 73     memset(sum,0,sizeof(sum));
 74     memset(num,0,sizeof(num));
 75     for (int i=1;i<m;i++) num[i]=(ll)(a[i].real()+0.5);
 76     //减掉取两个相同的组合
 77     for(int i =0;i<tmpn;i++)
 78     {
 79         num[l[i]+l[i]]--;
 80     }    
 81     for (int i=1;i<m;i++) num[i]/=2;
 82     sum[0]=0;
 83     
 84     for (int i=1;i<m;i++) sum[i]=sum[i-1]+num[i];
 85     
 86     ll cnt=0;
 87     n=tmpn;
 88     for (int i=0;i<n;i++)
 89     {
 90         cnt+=sum[m-1]-sum[l[i]];
 91         //减掉一个取大，一个取小的
 92         cnt-= (ll)(n-1-i)*i;
 93         //减掉一个取本身，另外一个取其它
 94         cnt-= (n-1);
 95         //减掉大于它的取两个的组合
 96         cnt-= (ll)(n-1-i)*(n-i-2)/2;
 97     }
 98     ll tot = (ll)n*(n-1)*(n-2)/6;
 99     printf("%.7lf
",(double)cnt/tot);
100 
101 }
102 
103 int main()
104 {
105     int T;
106     scanf("%d",&T);
107     while (T--)
108     {
109         init();
110            solve();
111         get_ans();
112     }
113     return 0;
114 }