Description

Input

Output

Sample Input

Sample Output

Solution

题意：给你$n$根木棍，问你任选三根能构成三角形的概率是多少。

写挂sb细节心态崩了

首先把读入的长度$a$数组开个桶$c$存下来，然后卷积一下$c$数组。可以发现卷完后的数组$c$就是“任选两根木棍（可以重复选）长度和为$c[i]$的方案数。”

因为有可能自己和自己算到一起，所以$c[a[i]*2]--$。因为$i+j$，$j+i$是一种，所以要$c[i]=c[i]/2$。

对$c$数组做一下前缀和，记为$sumd$。然后$sort$一下$a$数组，从小到大枚举，统计当$a[i]$为三角形最长边时的方案数，则另外两边之和$>a[i]$。$ans+=sumd[MAX*2]-sumd[a[i]]$

同时这些方案里面还有一些不合法的方案。

另外两条边两条均$>ai$，$ans-=(n-i)*(n-i-1)/2$

另外两条边一条$>ai$，一条$<ai$,$ans-=(n-i)*(i-1)$

另外两条边一条$=ai$，另一条随意，$ans-=n-1$

Code

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define N (400009) 7 #define LL long long 8 using namespace std; 9 10 LL T,n,ans,a[N],fn,l,r[N],d[N],sumd[N],MAX;11 12 double pi=acos(-1.0);13 struct complex14 {15     double x,y;16     complex (double xx=0,double yy=0)17     {18         x=xx; y=yy;19     }20 }c[N];21 22 complex operator + (complex a,complex b){
   return complex(a.x+b.x,a.y+b.y);}23 complex operator - (complex a,complex b){
   return complex(a.x-b.x,a.y-b.y);}24 complex operator * (complex a,complex b){
   return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}25 complex operator / (complex a,double b){
   return complex(a.x/b,a.y/b);}26 27 void FFT(int n,complex *a,int opt)28 {29     for (int i=0; i
          
           >1]>>1) | ((i&1)<<(l-1));67 FFT(fn,c,1);68 for (int i=0; i
           
            >=1, sumd[i]=sumd[i-1]+d[i];77 for (int i=1; i<=n; ++i)78 {79 ans+=sumd[MAX*2]-sumd[a[i]];80 ans-=(n-i)*(n-i-1)/2;//两条都大于a[i]81 ans-=(n-i)*(i-1);//一条大于，一条小于 82 ans-=n-1;//一条等于，一条随意 83 }84 printf("%.7lf\n",1.0*ans/(n*(n-1)*(n-2)/6));85 }86 }