HDU – 4609 3-idiots (FFT+母函数)

题意:给N个数,求任意选三个数能构成三角形的概率

分析:枚举两条边之和的复杂度\(O(N^2)\),显然不行,所以要更高效地做到枚举出两边之和.

所以用生成函数搭配FFT在\(O(NlogN)\)的时间内计算两边之和对应的个数.设\(cnt[i]\)为值\(i\)出现的次数.先不考虑元素的重复使用情况,则卷积的两个函数都是数组\(cnt[i]\).

设\(ans[i]\)为两边之和为i的个数,但需要减去重复计算的情况,每个ans[i]*2的项需要减1;重复枚举了\(ans[i]+ans[j]\)和\(ans[j]+ans[i]\),所以每个答案需要除2.之后处理出前缀和.

得到两边之和后,枚举三角形的最长边.将给定的\(a[i]\)排序.设当前枚举到值x时,另外两边之和可以是\([x+1,maxsum]\),而其中要减去一些不符合条件的情况:

1. 两边中有一条边枚举到了自己,减n-1;
2. 两边中的每条边都比自己大,减去(n-1-i)*(n-2-i)/2;
3. 一条边小于等于自己,一条边大于等于自己,减去(n-1-i)*i;

   因为最后要求概率,分母即\(C(n,3)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2e5 + 10;
const double PI = acos(-1.0);
struct Complex{
    double x, y;
    inline Complex operator+(const Complex b) const {
        return (Complex){x +b.x,y + b.y};
    }
    inline Complex operator-(const Complex b) const {
        return (Complex){x -b.x,y - b.y};
    }
    inline Complex operator*(const Complex b) const {
        return (Complex){x *b.x -y * b.y,x * b.y + y * b.x};
    }
} va[MAXN * 2 + MAXN / 2], vb[MAXN * 2 + MAXN / 2];
int lenth = 1, rev[MAXN * 2 + MAXN / 2];
int N, M;   // f 和 g 的数量
    //f g和 的系数
    // 卷积结果
    // 大数乘积
int f[MAXN],g[MAXN];
vector<LL> conv;
vector<LL> multi;
//f g
void init()
{
    int tim = 0;
    lenth = 1;
    conv.clear(), multi.clear();
    memset(va, 0, sizeof va);
    memset(vb, 0, sizeof vb);
    while (lenth <= N + M - 2)
        lenth <<= 1, tim++;
    for (int i = 0; i < lenth; i++)
        rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (tim - 1));
}
void FFT(Complex *A, const int fla)
{
    for (int i = 0; i < lenth; i++){
        if (i < rev[i]){
            swap(A[i], A[rev[i]]);
        }
    }
    for (int i = 1; i < lenth; i <<= 1){
        const Complex w = (Complex){cos(PI / i), fla * sin(PI / i)};
        for (int j = 0; j < lenth; j += (i << 1)){
            Complex K = (Complex){1, 0};
            for (int k = 0; k < i; k++, K = K * w){
                const Complex x = A[j + k], y = K * A[j + k + i];
                A[j + k] = x + y;
                A[j + k + i] = x - y;
            }
        }
    }
}
void getConv()
{
    init();
    for (int i = 0; i < N; i++)
        va[i].x = f[i];
    for (int i = 0; i < M; i++)
        vb[i].x = g[i];
    FFT(va, 1), FFT(vb, 1);
    for (int i = 0; i < lenth; i++)
        va[i] = va[i] * vb[i];
    FFT(va, -1);
    for (int i = 0; i <= N + M - 2; i++)
        conv.push_back((LL)(va[i].x / lenth + 0.5));
}void getMulti()
{
    getConv();
    multi = conv;
    reverse(multi.begin(), multi.end());
    multi.push_back(0);
    int sz = multi.size();
    for (int i = 0; i < sz - 1; i++){
        multi[i + 1] += multi[i] / 10;
        multi[i] %= 10;
    }
    while (!multi.back() && multi.size() > 1)
        multi.pop_back();
    reverse(multi.begin(), multi.end());
}int a[MAXN];
int cnt[MAXN];
LL tot[MAXN];int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int T,n; scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int mx = 0;
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;++i){
            scanf("%d",&a[i]);
            cnt[a[i]]++;
            mx = max(mx,a[i]);
        }
        N = M = mx+1;
        for(int i=0;i<=mx;++i){
            f[i] = g[i] = cnt[i];
        }
        getConv();
        int len = conv.size();
        for(int i=0;i<n;++i){
            --conv[a[i]<<1];         //同一个数选择两遍，减去
        }
        for(int i=0;i<len;++i){
            conv[i]>>=1;
        }
        for(int i=1;i<len;++i){
            conv[i] += conv[i-1];
        }
        sort(a,a+n);
        LL res=0;
        for(int i=0;i<n;++i){
            LL tmp = conv[len-1] - conv[a[i]];
            tmp -= n-1;
            tmp -=(LL)i*(n-i-1);
            if(n-i-1>1) tmp -= (LL)(n-i-1)*(n-i-2)/2;
            res += tmp;
        }
        printf("%.7f\n",(double)res*1.0/((LL)n*(n-1)*(n-2)/6));
    }
    return 0;
}