【BZOJ3513】idiots

DarkBZOJ https://darkbzoj.tk/problem/3513

---

Solution

也就是要求两边之和大于第三边

[a_x+a_y>a_k ]

记大于 (c) 的 (a_x+a_y) 有 (s_c) 个，等于 (c) 的 (a_k) 有 (b_c) 个
那么要求的就是

[sumlimits_{c=1}^{mx_a}s_cb_c ]

这不就完了？……其实不行，因为这并没有保证 (a_x e a_k) 且 (a_y e a_k)
那怎么办呢，

其实反过来就好了，不要记大于的，记小于等于的……。然后排除。
444
于是现在剩下要做的事情就是，怎么把 (s_c) 求出来
双指针是不行的，(O(n^2))
然后 (a_i) 级别比较小，可以开桶，仔细一想
明显就是一个卷积了

传统艺能：复数四则运算打错。。
另外最后忘记再反回去了，直接写了个 ans / tot
实际上是 (tot - ans) / tot

最后统计的时候各种各样的求和不要写错哦（

---

Code

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cctype>
using namespace std;
const int maxn = 5e5;
const int maxv = 2e5;
const double tpi = acos(-1.0);
int n_T, n, a[maxn], lim = 0, lgl, rev[maxn], mx;
long long tp[maxn], tb[maxn], tg[maxn];
long long ans;
struct cp
{
    double r, i;
    cp (double a = 0, double b = 0) { r = a, i = b; }
    cp operator + (cp b) { return cp(r + b.r, i + b.i); }
    cp operator - (cp b) { return cp(r - b.r, i - b.i); }
    cp operator * (cp b) { return cp(r * b.r - i * b.i, r * b.i + i * b.r); }
    void operator *= (cp b) { *this = *this * b; }
    void operator += (cp b) { r += b.r, i += b.i; }
    void operator -= (cp b) { r -= b.r, i -= b.i; }
} w, wn, t, b[maxn];
void fft(cp *a, int opt)
{
    for (int i = 0; i < lim; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int len, half = 1; half < lim; half = len)
    {
        len = half << 1;
        wn = cp(cos(tpi / half), sin(tpi / half) * opt);
        for (int pos = 0; pos < lim; pos += len)
        {
            w = cp(1, 0);
            for (int k = 0; k < half; ++k, w *= wn)
            {
                t = w * a[pos + half + k];
                a[pos + half + k] = a[pos + k] - t;
                a[pos + k] += t;
            }
        }
    }
    if (opt == -1) { for (int i = 0; i < lim; ++i) a[i].r /= lim; }
}
int main()
{
    cin >> n_T;
    while (n_T--)
    {
        for (int i = 0; i < lim; ++i)
        {
            b[i].r = 0;
            b[i].i = 0;
            tb[i] = 0;
        }
        cin >> n;
        lim = 1, lgl = mx = 0;
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            ++b[a[i]].r;
            ++tb[a[i]];
            if (a[i] > mx) mx = a[i];
        }
        mx <<= 1;
        while (lim <= mx) lim <<= 1, ++lgl;
        for (int i = 0; i < lim; ++i) 
        {
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lgl - 1));
        }
        fft(b, +1);
        for (int i = 0; i < lim; ++i) 
        {
            b[i] *= b[i];
        }
        fft(b, -1);
        for (int i = 2; i <= mx; ++i)
        {
            tp[i] = ((long long)(b[i].r + 0.5));
            if (!(i & 1)) tp[i] -= tb[i >> 1];
            tp[i] >>= 1;
        }
        ans = 0;
        tg[mx + 1] = 0;
        for (int i = mx; i >= 0; --i)
        {
            tg[i] = tg[i + 1] + tb[i];
        }
        for (int i = 2; i <= mx; ++i)
        {
            ans += tp[i] * tg[i];
        }
        long long tot = 1ll * n * (n - 1) * (n - 2) / 6;
        printf("%.7f
", 1.0 * (tot - ans) / tot);
    }
    // system("pause"); 
    return 0;
}