题意还是比较好懂。
给出若干个木棍的长度，问这些木棍构成三角形的可能性。
那么公式很容易知道
就是这些木棍组成三角形的所有情况个数 除以 从n个木棍中取3个木棍的情况数量C(n, 3) 即可
但是很显然分子不太好求。 因为木棍数据量是n^5
暂时没有办法，于是看到木棍的边长，数据量也是10^5，似乎预示着什么
那么我们可不可以这样：根据三角形的性质，两边之和大于第三边。我们就枚举每个木棍，假设该木棍是三角形中的最大边，然后看剩下的能构成三角形的两边的和有多少种情况。
这样一转换思路，就转到了求给出俩数组，然后从两个数组中各取出一个数，求相加的和各自有多少种。
由于数据量是10^5 ，所以我们可以把这两个数组中各个数的个数分别用数组num1, num2存起来。 然后刚才求相加的和有多少种就变成了求num1数组和num2之间的卷积了。
这就转变成了FFT了。 这样一来复杂度就降到了nlogn，到达了可以接受的范围
然后kuangbin巨巨的解释非常详细，我也是看了他的才懂点。http://www.cnblogs.com/kuangbin/archive/2013/07/24/3210565.html
然后就是代码了。 胡骏巨巨的模板果然厉害！！
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
#define L(x) (1 << (x))
const double PI = acos(-1.0);
const int Maxn = 400001;
double ax[Maxn], ay[Maxn], bx[Maxn], by[Maxn];
long long num[Maxn];
int a[Maxn/4];
long long sum[Maxn];
int revv(int x, int bits)
{
int ret = 0;
for (int i = 0; i < bits; i++)
{
ret <<= 1;
ret |= x & 1;
x >>= 1;
}
return ret;
}
void fft(double * a, double * b, int n, bool rev)
{
int bits = 0;
while (1 << bits < n) ++bits;
for (int i = 0; i < n; i++)
{
int j = revv(i, bits);
if (i < j)
swap(a[i], a[j]), swap(b[i], b[j]);
}
for (int len = 2; len <= n; len <<= 1)
{
int half = len >> 1;
double wmx = cos(2 * PI / len), wmy = sin(2 * PI / len);
if (rev) wmy = -wmy;
for (int i = 0; i < n; i += len)
{
double wx = 1, wy = 0;
for (int j = 0; j < half; j++)
{
double cx = a[i + j], cy = b[i + j];
double dx = a[i + j + half], dy = b[i + j + half];
double ex = dx * wx - dy * wy, ey = dx * wy + dy * wx;
a[i + j] = cx + ex, b[i + j] = cy + ey;
a[i + j + half] = cx - ex, b[i + j + half] = cy - ey;
double wnx = wx * wmx - wy * wmy, wny = wx * wmy + wy * wmx;
wx = wnx, wy = wny;
}
}
}
if (rev)
{
for (int i = 0; i < n; i++)
a[i] /= n, b[i] /= n;
}
}
int solve(long long a[], int na, long long ans[])
{
int len = na, ln;
for(ln = 0; L(ln) < na; ++ln);
len=L(++ln);
for(int i = 0; i < len; ++i)
{
if (i >= na) ax[i] = 0, ay[i] = 0;
else ax[i] = a[i], ay[i] = 0;
}
fft(ax, ay, len, 0);
for(int i=0; i<len; ++i)
{
double cx = ax[i] * ax[i] - ay[i] * ay[i];
double cy = 2 * ax[i] * ay[i];
ax[i] = cx, ay[i] = cy;
}
fft(ax, ay, len, 1);
for(int i=0; i<len; ++i)
ans[i] = ax[i] + 0.5;
return len;
}
int main()
{
int T;
int n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(num, 0, sizeof(num));
for(int i = 0;i < n;i++)
{
scanf("%d", &a[i]);
num[a[i]]++;
}
sort(a, a + n);
int len1 = a[n - 1] + 1;
solve(num, len1, num);
int len = 2 * a[n - 1];
for(int i = 0;i < n;i++) //减掉取两个相同的组合
num[a[i] + a[i]]--;
for(int i = 1;i <= len;i++) //选择的无序，除以2
num[i] /= 2;
sum[0] = 0;
for(int i = 1;i <= len;i++)
sum[i] = sum[i - 1] + num[i];
long long cnt = 0;
for(int i = 0;i < n; i++)
{
cnt += sum[len] - sum[a[i]];
cnt -= (long long)(n - 1 - i) * i;//减掉一个取大，一个取小的
cnt -= (n - 1); //减掉一个取本身，另外一个取其它
cnt -= (long long)(n - 1 - i)*(n - i - 2) / 2; //减掉大于它的取两个的组合
}
//总数
long long tot = (long long)n * (n - 1) * (n - 2) / 6;
printf("%.7lf
",(double)cnt / tot);
}
return 0;
}