题意还是比较好懂。
给出若干个木棍的长度，问这些木棍构成三角形的可能性。
那么公式很容易知道
就是这些木棍组成三角形的所有情况个数 除以 从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++) //选择的无序，除以2num[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\n",(double)cnt / tot);}return 0;
}