题目：

答案就是随便选三条边的方案 - 不合法的方案。

不合法的方案就是算出 x+y = k 的方案数 g[ k ]，对于每个长度 z ，不合法方案+=\( \sum\limits_{k=0}^{z}g[k] \)

注意 FFT 之后偶数项 k 算上了取长度为 k/2 的同一条边两遍的方案，要去重。

随便选三条边的 n*(n-1)*(n-2) 会把同一个 x , y , z 算6遍，而枚举 z 会把同一个 x , y , z 算两遍，所以要乘3。

注意减去的时候乘上长度为 z 的边的个数。

#include
     
      #include
      
       #include
       
        #include
        
         #define db double#define ll long longusing namespace std;const int N=1e5+5,M=(1<<18)+5;const db pi=acos(-1);int T,n,len,r[M],f[N];struct cpl{db x,y;}a[M],I;cpl operator+ (cpl a,cpl b){
   return (cpl){a.x+b.x,a.y+b.y};}cpl operator- (cpl a,cpl b){
   return (cpl){a.x-b.x,a.y-b.y};}cpl operator* (cpl a,cpl b){
   return (cpl){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}int Mx(int a,int b){
   return a>b?a:b;}int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
   if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}void fft(cpl *a,bool fx){  for(int i=0;i
         
          >1;      cpl wn=(cpl){ cos(pi/m),fx?-sin(pi/m):sin(pi/m) };      for(int i=0;i
          
           >1;i
           
            >1]>>1)+((i&1)?j:0); fft(a,0); for(int i=0;i
            
             >1]:0) )*3; ans-=lj*f[i];//*f[i]!! } printf("%.7f\n",(db)ans/sm); } return 0;}