【题意】
有T组数据
每组数据给出n条线段，问任意取三条，可以组成三角形的概率
【输入】
开头一行输入T（T<=100）
下来T组数据，每组数据第一行输入一个n（3<=n<=10^5）
第二行输入n个数，表示n条线段
线段长度（1<=n<=10^5）
【输出】
每组数据输出一个数p
表示可以组成三角形的概率
保留七位小数
【样例输入】
2
4
1 3 3 4
4
2 3 3 4
【样例输出】
0.5000000
1.0000000
【题解】
一开始看到这题没觉得是FFT。。对于一个数学困难户我就orz了kuangbin大牛的题解。。
最后看回来真的是666
首先我们把题目给出的棍子用num数组存起来
num[i]表示长度为i的棍子有几根
然后。。根据数学原理。自乘一次，我们就得到了随便取两根，能得到的长度的方案数，对不对！
当然，和自己组合是不行的。。所以后续计算的时候要处理一下。此外，先选T1后选T2和先选T2后选T1的方案，也是一样的。所以说处理完后还要除以2
之后我们可以开始找组合了对吧。
首先先将木棍们从小到大排序
规定一点：我们选的木棍，一定是三根里面最长的！
那么For每根木棍，取两根长度>a[i]的方案数
但是有一点坑的地方是
1：不能取一个比i大一个比i小的木棍
2：取了本身i及其他的
3：取了两个都大于i的木棍
最后减掉，再用能组成三角形的方案数/总的方案数
就得到能组成三角形的概率啦~
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const double PI=acos(-1.0);
const int MAXN=810000;
typedef long long LL;
struct Complex
{double r,i;Complex(){}Complex(double _r,double _i){r=_r;i=_i;}friend Complex operator +(const Complex &x,const Complex &y){
return Complex(x.r+y.r,x.i+y.i);}friend Complex operator -(const Complex &x,const Complex &y){
return Complex(x.r-y.r,x.i-y.i);}friend Complex operator *(const Complex &x,const Complex &y){
return Complex(x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r);}
};
int R[MAXN];
void fft(Complex *y,int len,int on)
{for(int i=0;i<len;i++)if(i<R[i])swap(y[i],y[R[i]]);for(int i=1;i<len;i<<=1){Complex wn(cos(PI/i),on*sin(PI/i));for(int j=0;j<len;j+=(i<<1)){Complex w(1.0,0.0);for(int k=0;k<i;k++){Complex u=y[j+k];Complex v=y[j+k+i]*w;y[j+k]=u+v;y[j+k+i]=u-v;w=w*wn;}}}if(on==-1)for(int i=0;i<len;i++)y[i].r/=len;
}
LL sum[MAXN],num[MAXN];int x[MAXN];
Complex a[MAXN];
int main()
{int T,n,m,L,len;scanf("%d",&T);while(T--){memset(num,0,sizeof(num));scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&x[i]);num[x[i]]++;}sort(x,x+n);L=0;m=x[n-1]+1;for(len=1;len<=m*2;len<<=1)L++;for(int i=0;i<len;i++)R[i]=(R[i>>1]>>1)|(i&1)<<(L-1);for(int i=0;i<m;i++)a[i]=Complex(num[i],0);for(int i=m;i<len;i++)a[i]=Complex(0,0);fft(a,len,1);for(int i=0;i<len;i++)a[i]=a[i]*a[i];fft(a,len,-1);for(int i=0;i<len;i++)num[i]=(LL)(a[i].r+0.5);len=2*x[n-1];for(int i=0;i<n;i++)num[x[i]+x[i]]--;for(int i=1;i<=len;i++)num[i]/=2;sum[0]=0;for(int i=1;i<=len;i++)sum[i]=sum[i-1]+num[i];LL cnt=0;for(int i=0;i<n;i++){cnt+=sum[len]-sum[x[i]];cnt-=(n-1);cnt-=(long long)(n-1-i)*i;cnt-=(long long)(n-1-i)*(n-2-i)/2;}LL tot=(LL)(n)*(n-1)*(n-2)/6;printf("%.7lf\n",(double)cnt/tot);}return 0;
}传送门：http://caioj.cn/problem.php?id=1454