正难则反,首先概率就是\(\frac{合法的方案数}{总的方案数}\)=\(\frac{总的方案数-不合法的方案数}{总的方案数}\),
统计不合法的方案数只需要 两个较短的边的长度和\(\le\)较长的边,用t[i]表示长度大于等于i的木棍的数量,f[i]为长度为i的木棍的数量,g[i]表示选出两根木棍组成和为i的方案数,很明显g等于f卷上f,
注意自己不能卷自己,直接在最后让自己卷自己的方案数减去就行了。
然后\(\displaystyle \sum \frac{g[i]}{2} \times t[i]\)就是不合法的方案数了,除2是因为 先选木棍1后选木棍2 和 先选木棍2后选木棍1 是一样的。
bzoj数据比较毒瘤,NTT超时了,得用FFT才能过…
时间复杂度O(n log n).
#include<bits/stdc++.h>
#define DB double
#define LL long long
#define AK 0
#define IOI ;
using namespace std;
int T, n, x, maxx, lim;
LL ans, tot;
const int N = 400010;
const DB PI = acos(-1);
int r[N], t[N];
LL g[N];//f一根的长度为i的方案数 g两根组成i的方案数 t一根长度大于等于i的方案数
inline int read()
{
int res = 0; char ch = getchar(); bool XX = false;
for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
return XX ? -res : res;
}
struct xu
{
DB x, y;
xu(DB X = 0, DB Y = 0) {x = X, y = Y;}
friend xu operator +(const xu &a, const xu &b)
{return (xu) {a.x + b.x, a.y + b.y};}
friend xu operator -(const xu &a, const xu &b)
{return (xu) {a.x - b.x, a.y - b.y};}
friend xu operator *(const xu &a, const xu &b)
{return (xu) {a.x*b.x - a.y*b.y, a.x*b.y + a.y*b.x};}
} f[N];
void FFT(xu *A, int lim, int opt)
{
for (int i = 0; i < lim; ++i)
r[i] = (r[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
for (int i = 0; i < lim; ++i)
if (i < r[i])swap(A[i], A[r[i]]);
int len;
xu wn, w, x, y;
for (int mid = 1; mid < lim; mid <<= 1)
{
len = mid << 1;
wn = (xu) {cos(PI / mid), opt*sin(PI / mid)};
for (int j = 0; j < lim; j += len)
{
w = (xu) {1, 0};
for (int k = j; k < j + mid; ++k, w = w * wn)
{
x = A[k]; y = A[k + mid] * w;
A[k] = x + y; A[k + mid] = x - y;
}
}
}
}
void YYch()
{
for (int i = 0; i <= lim; ++i)f[i] = g[i] = t[i] = 0;
maxx = 0; lim = 1; ans = tot = 0;
}
inline void treAKer()
{
YYch();
cin >> n;
for (int i = 1; i <= n; ++i)
{
maxx = max(maxx, x = read());
f[x].x++; t[x]++; g[x << 1]--;
}
for (int i = maxx; i >= 1; --i)t[i] += t[i + 1];
while (lim <= (maxx << 1))lim <<= 1;
FFT(f, lim, 1);
for (int i = 0; i < lim; ++i)f[i] = f[i] * f[i];
FFT(f, lim, -1);
for (int i = 0; i < lim; ++i)g[i] += (int)(f[i].x / lim + 0.5);
tot = (LL)n * (n - 1) * (n - 2) / 6;
for (int i = 0; i < lim; ++i)ans += (g[i] >> 1) * t[i];
printf("%.7f\n", (double)(tot - ans) / tot);
}
int main()
{
cin >> T;
while (T--)treAKer();
return AK IOI;
}