解题报告：
记录 A_i 为长度为 i 的树枝的数量，并让 A 对它本身做 FFT，得到任意选两个树枝能得到的各个和的数量。枚举第三边，
计算出所有两边之和大于第三条边的方案数，并把前两条边包含最长边的情况减掉就是答案。
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #include<vector> 8 #define ll __int64 9 #define pi acos(-1.0) 10 using namespace std; 11 const int MAX = 400002; 12 //复数结构体 13 struct complex{ 14 double r,i; 15 complex(double R=0,double I=0){ 16 r=R;i=I; 17 } 18 complex operator+(const complex &a){ 19 return complex(r+a.r,i+a.i); 20 } 21 complex operator-(const complex &a){ 22 return complex(r-a.r,i-a.i); 23 } 24 complex operator*(const complex &a){ 25 return complex(r*a.r-i*a.i,r*a.i+i*a.r); 26 } 27 }; 28 /* 29 *进行FFT和IFFT前的反转变换 30 *位置i和i的二进制反转后位置互换，(如001反转后就是100) 31 *len必须去2的幂 32 */ 33 void change(complex x[],int len){ 34 int i,j,k; 35 for(i = 1, j = len>>1; i <len-1; i++){ 36 if (i < j) swap(x[i],x[j]); 37 //交换互为小标反转的元素，i<j保证交换一次 38 //i做正常的+1,j做反转类型的+1，始终i和j是反转的 39 k = len>>1; 40 while (j >= k){ 41 j -= k; 42 k >>= 1; 43 } 44 if (j < k) j += k; 45 } 46 } 47 /* 48 *做FFT O(nLogn) 49 *len必须为2^n形式，不足则补0 50 *on=1时是DFT，on=-1时是IDFT 51 */ 52 void fft (complex x[],int len,int on){ 53 change(x,len); //调用反转置换 54 for (int i=2;i<=len;i<<=1){//控制层次 55 //初始化单位复根 56 complex wn(cos(on*2*pi/i),sin(on*2*pi/i)); 57 for (int j=0;j<len;j+=i){ 58 complex w(1,0); //初始化旋转因子 59 for (int k=j;k<j+i/2;k++){ 60 complex u = x[k]; 61 complex t = w*x[k+i/2]; 62 x[k] = u+t; 63 x[k+i/2] = u-t; 64 w = w*wn; //更新旋转因子 65 } 66 } 67 } 68 if (on == -1){ 69 for (int i=0;i<len;i++){ 70 x[i].r /= len; 71 } 72 } 73 } 74 complex x1[MAX]; 75 int a[MAX/4]; 76 ll num[MAX],sum[MAX]; 77 int main() 78 { 79 int i,j,k,len1,len2,len,t,n; 80 cin>>t; 81 while(t--){ 82 cin>>n; 83 memset(num,0,sizeof(num)); 84 for (i=0;i<n;i++){ 85 cin>>a[i]; 86 num[a[i]]++; 87 } 88 sort(a,a+n); 89 len1 = a[n-1]+1; 90 len = 1; 91 while (len<2*len1) len<<=1; 92 for (i=0;i<len1;i++){ 93 x1[i] = complex(num[i],0); 94 } 95 for (i=len1;i<len;i++){ 96 x1[i] = complex(0,0); 97 } 98 fft(x1,len,1); 99 for (i=0;i<len;i++){ 100 x1[i] = x1[i]*x1[i]; 101 } 102 fft(x1,len,-1); 103 for (i=0;i<len;i++){ 104 num[i] = (ll)(x1[i].r+0.5); 105 } 106 len = 2*a[n-1]; 107 for (i=0;i<n;i++) 108 num[a[i]+a[i]]--;//减去自己与自己的组合 109 for (i=1;i<=len;i++) 110 num[i] /= 2;//考虑a+b,b+a的组合，个数/2 111 sum[0] = 0; 112 for (i=1;i<=len;i++){ 113 sum[i] = sum[i-1]+num[i];//求前项和 114 } 115 ll cnt = 0; 116 for (i=0;i<n;i++){ 117 cnt += sum[a[i]];//a+b<=c的个数 118 } 119 ll total = (ll)n*(n-1)*(n-2)/6; 120 printf("%.7lf ",1-(double)cnt/total); 121 } 122 return 0; 123 }