要求组合的方法显然我们需要对桶卷积，即设$F(x)=\sum\limits_{i=1}^{maxx}x^{cnt[i]}$，然后我们初步的先把$F^2(x)$卷出来，表示选两条边。然后我们发现如果用“两边之和大于第三边”来求，那么小于这两条边的可能不是最长的，所以应该枚举大于这两条边的来容斥
注意题目中提到了不能选重复的，所以对于所有指数为偶数的项去重，还有题目要求是无序地选
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=,K=4e5;
const double pai=acos(-);
struct cpx
{
double x,y;
}a[N];
cpx operator + (cpx a,cpx b)
{
return (cpx){a.x+b.x,a.y+b.y};
}
cpx operator - (cpx a,cpx b)
{
return (cpx){a.x-b.x,a.y-b.y};
}
cpx operator * (cpx a,cpx b)
{
double x1=a.x,x2=b.x,y1=a.y,y2=b.y;
return (cpx){x1*x2-y1*y2,x1*y2+x2*y1};
}
long long cnt[N],tot,ans;
int mem[N],rev[N],lgg[N];
double Sin[M],Cos[M];
int n,m,T,rd;
int Round(double x)
{
return (int)(x+0.5);
}
void Prework()
{
scanf("%d",&T);
for(int i=;i<=K;i++)
lgg[i]=lgg[i>>]+;
for(int i=;i<=;i++)
Sin[i]=sin(*pai/(<<i)),Cos[i]=cos(*pai/(<<i));
}
void Trans(cpx *c,int t)
{
for(int i=;i<n;i++)
if(rev[i]>i) swap(c[rev[i]],c[i]);
for(int i=;i<=n;i<<=)
{
int len=i>>;
cpx omg=(cpx){Cos[lgg[i]],Sin[lgg[i]]*t};
for(int j=;j<n;j+=i)
{
cpx ori=(cpx){,},tmp;
for(int k=j;k<j+len;k++,ori=ori*omg)
tmp=ori*c[k+len],c[k+len]=c[k]-tmp,c[k]=c[k]+tmp;
}
}
if(t==-) for(int i=;i<n;i++) c[i].x/=n;
}
int main()
{
Prework();
while(T--)
{
scanf("%d",&n);
memset(mem,,sizeof mem),m=;
for(int i=;i<=n;i++)
{
scanf("%d",&rd);
mem[rd]++,m=max(m,rd);
}
ans=tot=1ll*n*(n-)*(n-)/,n=; while(n<=m*) n<<=;
for(int i=;i<n;i++) a[i].x=mem[i],a[i].y=;
for(int i=;i<n;i++) rev[i]=(rev[i>>]>>)+(i&)*(n>>);
Trans(a,);
for(int i=;i<n;i++) a[i]=a[i]*a[i];
Trans(a,-);
for(int i=;i<=m;i++) cnt[i]=Round(a[i].x);
for(int i=;i<=m;i++)
{
if(i%==) cnt[i]-=mem[i>>];
cnt[i]>>=,cnt[i]+=cnt[i-];
}
for(int i=;i<=m;i++) ans-=cnt[i]*mem[i];
printf("%.7f\n",(double)ans/tot);
}
return ;
}