3-idiots-HDU4609(FFT)

题目链接

3-idiots-HDU4609

思路

从一个数列中随机取3个然后形成三角形的概率，因为边长的范围是1e5之内，所以如果两条边相加最长也就是2e5，于是我们考虑使用FFT处理出任意两条边的和。每一个序列值对应一个多项式的系数+1，例如样例的[1 3 3 4]我们就可以得到

$$F(x)=x+2x^3+x^4$$

如果我们进行多项式乘法F(x)*F(x)可以得到对应的多项式

$$F(x)*F(x)=x^2+4x^4+2x^5+4x^6+4x^7+x^8$$

也就是得到了[2 4 4 4 4 5 5 6 6 6 6 7 7 7 7 8]的序列，当然我们需要帅选去重，先减去自身与自身的(1,1)(3,3)(3,3)(4,4)，然后再晒去重复的，例如选择(4,3)和(3,4)是一样的，就让他们除以2，这样就能得到最后两条边的边长的式子.
统计答案，我们对每一条边，分别让它作为这个三角形的最大值，然后加上ans+sum[len]-sum[a[i]],因为前提这条边是最大的边，所以我们减去这条边是第二大的边的情况，也就是有一条比它大，有一条比它小ans-=(n-i-1)*i,前面是比它大的，后面是比它小的，然后再减去它自身组成的边，也就是它本身和其他(n-1)条边的组合，ans-=(n-1)，然后减去第三大边的情况，也就是这条边是最小的情况ans-=(n-i-1)(n-i-2)/2,其实就是从比它大的n-i-1条中先选取一条，再从剩下的n-i-2条中选取一条，然后去除重复的/2，就可以得到最终的答案了。

代码实现

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define ll long long 
#define pi acos(-1)
const int N = 2e5+10;
ll a[N],r[N],b[2*N],sum[2*N];
ll num[N];
struct cp
{
    double r,i;
    cp(double _r = 0,double _i = 0)
    {
        r = _r; i = _i;
    }
    cp operator +(const cp &b)
    {
        return cp(r+b.r,i+b.i);
    }
    cp operator -(const cp &b)
    {
        return cp(r-b.r,i-b.i);
    }
    cp operator *(const cp &b)
    {
        return cp(r*b.r-i*b.i,r*b.i+i*b.r);
    }
}F[N*2];
void FFT(cp *s,int n,int inv)
{
	for(int i=0;i<n;i++)if(i<r[i])swap(s[i],s[r[i]]);
	for(ll len=2;len<=n;len*=2){
		cp wn=cp(cos(2.0*pi/len),inv*sin(2.0*pi/len));
		for(ll st=0;st<n;st+=len){
		cp w=cp(1.0,0.0);
		for(ll i=st;i<st+len/2;i++,w=w*wn){
				cp x = s[i];
				cp y = w*s[i+len/2];
				s[i]=x+y;
				s[i+len/2]=x-y;
		}
	}
	}
	if(inv==-1){
		for(int i=0;i<n;i++)
		s[i].r/=n;
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		memset(num,0,sizeof(num));
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
			num[a[i]]++;
		}
		sort(a,a+n);
		int len1 = a[n-1]+1;
		for(int i=0;i<len1;i++){
			F[i].r=num[i];
			F[i].i=0;
		}
		int len=1,bit=0;
		while(len<2*len1)len<<=1,bit++;
		for(int i=0;i<len;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(bit-1));
		for(int i=len1;i<len;i++){
			F[i].r=0;
			F[i].i=0;
		}
		FFT(F,len,1);
		for(int i=0;i<len;i++)
		F[i]=F[i]*F[i];
		FFT(F,len,-1);
		for(int i=0;i<len;i++)b[i]=(ll)(F[i].r+0.5);
		len=2*a[n-1];
		for(int i=0;i<n;i++)b[a[i]+a[i]]--;
		for(int i=0;i<=len;i++)b[i]/=2;
		b[0]=0;
		for(int i=1;i<=len;i++)b[i]+=b[i-1];
		ll ans = 0;
		for(int i=0;i<n;i++){
	    ans+=b[len]-b[a[i]];
		ans-=1ll*(n-i-1)*i;
		ans-= (n-1);
		ans-=1ll*(n-i-1)*(n-i-2)/2;	
		}
		ll tot = 1ll*n*(n-1)*(n-2)/6;
		printf("%.7lf\n",(double)ans/tot);
	}
}