laekov

居然写了一半手贱就把所有东西都弄没了。严重地不开心。

既然这样那么简单说吧。

长度≤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());

}