居然写了一半手贱就把所有东西都弄没了。严重地不开心。
既然这样那么简单说吧。
长度≤10^5这个条件在bzoj上没说。
用fft求出长度和为leni的组数。
枚举第三根火柴，可行的是（它作为最长的总组合数 - （长度≤它的组合数））那么多组。
fft必需常数够小。不写蝴蝶会tle。
#include <cstdio>
#include <cmath>
#include <cctype>
#include <memory.h>
#include <algorithm>
using namespace std;
typedef long long qw;
#define readInt(_s_) {\
int _d_;\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
struct cplx {
double r, i;
inline cplx() {
r = 0, i = 0;
}
inline cplx(double r0, double i0) {
r = r0, i = i0;
}
inline cplx operator =(const cplx& a) {
r = a. r, i = a. i;
return *this;
}
inline cplx operator +(const cplx& a) {
return cplx(r + a. r, i + a. i);
}
inline cplx operator -(const cplx& a) {
return cplx(r - a. r, i - a. i);
}
inline cplx operator *(const cplx& a) {
return cplx(r * a. r - i * a. i, r * a. i + i * a. r);
}
};
#define pow2(x) (1<<(x))
#define _l (long long int)
const int maxn = 300009;
const double pi = asin(1) * 2.0;
int n, x[maxn], cn[maxn];
qw v[maxn];
cplx a[maxn], b[maxn];
int cBit(int x) {
int s = 0;
while (x >>= 1)
++ s;
return s;
}
void rader(cplx* a, int n) {
for (int i = 1, j = (n >> 1), k; i < n - 1; ++ i) {
if (i < j)
swap(a[i], a[j]);
k = n >> 1;
while (j >= k) {
j -= k;
k >>= 1;
}
if (j < k)
j += k;
//printf("%d %d\n", k, j);
}
}
void fft(cplx* a, int n, bool rv = 0) {
rader(a, n);
for (int h = 2; h <= n; h <<= 1) {
cplx ww(cos(pi * 2 / (double)h), sin(pi * 2 / (double)h));
if (rv)
ww. i = - ww. i;
for (int i = 0; i < n; i += h) {
cplx w(1, 0);
for (int j = i; j < i + (h >> 1); ++ j) {
cplx x = a[j], y = a[j + (h >> 1)] * w;
a[j] = x + y;
a[j + (h >> 1)] = x - y;
w = w * ww;
}
}
}
}
double sov() {
int m = 0, t;
memset(cn, 0, sizeof(cn));
readInt(n);
for (int i = 0; i < n; ++ i) {
readInt(x[i]);
++ cn[x[i]];
m = max(m, x[i]);
}
for (t = 1; t <= m; t <<= 1);
t <<= 1;
for (int i = 0; i < t; ++ i)
a[i] = cplx(cn[i], 0);
fft(a, t);
for (int i = 0; i < t; ++ i)
b[i] = a[i] * a[i];
fft(b, t, 1);
qw tot = _l n * (n - 1) * (n - 2) / 6, cnt = 0;
for (int i = 0; i < t; ++ i)
v[i] = (qw)(b[i]. r / t + 0.499);
for (int i = 0; i < n; ++ i)
-- v[x[i] << 1];
for (int i = 1; i < t; ++ i)
v[i] += v[i - 1];
sort(x, x + n);
for (int i = 2; i < n; ++ i)
cnt += (_l i * (i - 1) - v[x[i]]) >> 1;
return (double)cnt / tot;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int t;
readInt(t);
while (t --)
printf("%.7lf\n", sov());
}