题目链接:点击打开链接
解题思路：假设三角形最长边是m,那么只要使得其他两边的和大于m,这三边就一定能组成三角形，反之不能。那么求任意两边的和就用到了fft，把输入的数x看做是第x项系数加1.通过自己卷自己的方式得到任意两边的和再去掉重复的，包括一根木头同时用了两次的情况和顺序颠倒的情况要除以二。用ans[i]记录任意两条木头的和不超过i的方案数。那么当x做最长边时,不符合条件的方案数就是ans[x]。
#include<bits/stdc++.h> #include<time.h> using namespace std; typedef long long ll; typedef complex<double> comp; const double pi = acos(-1); const int mx = 3e5 + 10; int n,m,d[mx],c[mx],rev[mx]; ll ans[mx]; comp a[mx]; void get_rev(int len) { for(int i=1;i<(1<<len);i++) rev[i] = (rev[i>>1]>>1)|((i&1)<<(len-1)); } void fft(comp *p,int len,int v) { for(int i=0;i<len;i++) if(i<rev[i]) swap(p[i],p[rev[i]]); for(int i=1;i<len;i<<=1){ comp tep = exp(comp(0,v*pi/i)); for(int j=0;j<len;j+=(i<<1)){ comp mul(1,0); for(int k=j;k<i+j;k++){ comp x = p[k]; comp y = mul*p[k+i]; p[k] = x + y,p[k+i] = x - y; mul *= tep; } } } if(v==-1) for(int i=0;i<len;i++) p[i] /= len; } int main() { int t;scanf("%d",&t); while(t--){ scanf("%d",&n); int ma = 0,x; memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); for(int i=0;i<n;i++){ scanf("%d",&x); ma = max(x+1,ma); c[x]++,d[2*x]++; } for(int i=0;i<ma;i++) a[i] = comp(c[i],0); int lens = 0,sum; while((1<<lens)<2*ma-1) lens++; sum = (1<<lens); get_rev(lens); fft(a,sum,1); for(int i=0;i<sum;i++) a[i] = a[i]*a[i]; fft(a,sum,-1); for(int i=0;i<sum;i++) ans[i] = (a[i].real()+0.5),ans[i] -= d[i]; for(int i=1;i<sum;i++) ans[i] /= 2,ans[i] += ans[i-1]; ll ret = 0,acd = 1ll*n*(n-1)*(n-2)/6; for(int i=0;i<=ma;i++) ret += c[i]*ans[i]; printf("%.7lf\n",1-(1.0*ret/acd)); } return 0; }