1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
| ##include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef long double ld; typedef pair<int, int> pdd;
##define INF 0x3f3f3f3f ##define lowbit(x) x & (-x) ##define mem(a, b) memset(a , b , sizeof(a)) ##define FOR(i, x, n) for(int i = x;i <= n; i++)
const double PI = acos(-1);
const int N = 4e5 + 10;
struct Complex { double r, i; Complex() {r == 0; i = 0;}; Complex(double real, double imag) : r(real), i(imag) {}; }A[N], B[N];
Complex operator + (Complex a, Complex b) { return Complex(a.r + b.r, a.i + b.i); }
Complex operator - (Complex a, Complex b) { return Complex(a.r - b.r, a.i - b.i); }
Complex operator * (Complex a, Complex b) { return Complex(a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r); }
int rev[N], len, lim = 1;
void FFT(Complex *a, int opt) { for(int i = 0;i < lim; i++) { if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int dep = 1;dep <= log2(lim); dep++) { int m = 1 << dep; Complex wn = Complex(cos(2.0 * PI / m), opt * sin(2.0 * PI / m)); for(int k = 0;k < lim; k += m) { Complex w = Complex(1, 0); for(int j = 0;j < m / 2; j++) { Complex t = w * a[k + j + m / 2]; Complex u = a[k + j]; a[k + j] = u + t; a[k + j + m / 2] = u - t; w = w * wn; } } } if(opt == -1) { for(int i = 0;i < lim; i++) a[i].r /= lim; } }
int getBit(int n) { while(lim < (n << 1)) { lim <<= 1; len++; } for(int i = 0;i < lim; i++) rev[i] = (rev[i >> 1] >> 1) ((i & 1) << (len - 1)); }
ll a[N], cnt[N]; ll sum[N], num[N];
void solve() { int T; scanf("%d",&T); while(T--) { mem(rev, 0); mem(A, 0); mem(num, 0); mem(cnt, 0); int n; len = 0, lim = 1; scanf("%d",&n); for(int i = 0;i < n; i++) { scanf("%lld",&a[i]); cnt[a[i]]++; } sort(a, a + n); getBit(a[n - 1] + 1); int Max = a[n - 1] * 2; for(int i = 0;i <= a[n - 1]; i++) { A[i].r = cnt[i]; } FFT(A, 1); for(int i = 0;i < lim; i++) { A[i] = A[i] * A[i]; } FFT(A, -1); for(int i = 0;i < lim; i++) { num[i] = A[i].r = (ll)(A[i].r + 0.5); } for(int i = 0;i < n; i++) { num[a[i] + a[i]]--; } sum[0] = 0; for(int i = 0;i <= Max; i++) { num[i] /= 2; sum[i] = sum[i - 1] + num[i]; } ll ans = 0; for(int i = 0;i < n; i++) { ans += sum[Max] - sum[a[i]]; } for(int i = 0;i < n; i++) { ans -= ll(n - i - 1) * (n - i - 2) / 2; ans -= ll(n - i - 1) * i; ans -= ll(n - 1); } ll t = 1ll * n * (n - 1) * (n - 2) / 6;
printf("%.7lf\n",(double)ans / t); } }
signed main() { ios_base::sync_with_stdio(false); ##ifdef FZT_ACM_LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); signed test_index_for_debug = 1; char acm_local_for_debug = 0; do { if (acm_local_for_debug == '$') exit(0); if (test_index_for_debug > 20) throw runtime_error("Check the stdin!!!"); auto start_clock_for_debug = clock(); solve(); auto end_clock_for_debug = clock(); cout << "Test " << test_index_for_debug << " successful" << endl; cerr << "Test " << test_index_for_debug++ << " Run Time: " << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl; cout << "--------------------------------------------------" << endl; } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug)); ##else solve(); ##endif return 0; }
|