HDU4609:3-idiots(FFT)

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<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 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 complex
14 {
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<n; ++i)
30         if (i<r[i])
31             swap(a[i],a[r[i]]);
32     for (int k=1; k<n; k<<=1)
33     {
34         complex wn=complex(cos(pi/k),opt*sin(pi/k));
35         for (int i=0; i<n; i+=(k<<1))
36         {
37             complex w=complex(1,0);
38             for (int j=0; j<k; ++j,w=w*wn)
39             {
40                 complex x=a[i+j], y=w*a[i+j+k];
41                 a[i+j]=x+y; a[i+j+k]=x-y;
42             }
43         }
44     }
45     if (opt==-1) for (int i=0; i<n; ++i) a[i]=a[i]/n;
46 }
47 
48 int main()
49 {
50     scanf("%lld",&T);
51     while (T--)
52     {
53         memset(c,0,sizeof(c));
54         memset(r,0,sizeof(r));
55         l=0; ans=0; MAX=0;
56         scanf("%lld",&n);
57         for (int i=1; i<=n; ++i)
58         {
59             scanf("%lld",&a[i]);
60             c[a[i]].x++;
61         }
62         sort(a+1,a+n+1); MAX=a[n];
63         fn=1;
64         while (fn<=MAX*2) fn<<=1, l++;
65         for (int i=0; i<fn; ++i)
66             r[i]=(r[i>>1]>>1) | ((i&1)<<(l-1));
67         FFT(fn,c,1);
68         for (int i=0; i<fn; ++i)
69             c[i]=c[i]*c[i];
70         FFT(fn,c,-1);
71         for (int i=1; i<fn; ++i)
72             d[i]=((LL)(c[i].x+0.5));//一开始括号里写成int了…… 
73         for (int i=1; i<=n; ++i)
74             d[a[i]*2]--;
75         for (int i=1; i<=MAX*2; ++i)
76             d[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
",1.0*ans/(n*(n-1)*(n-2)/6));
85     }
86 }