HDU 4609——3-idiots

淩亂°似流年 2022-07-19 02:39 20阅读 0赞

题意：

给定n个数，随机从这n个数中取3个数，问能组成三角形的概率是多少？

思路：

首先把统计这n个数出现的个数，那么会得到一个向量，这个向量的自我的乘积就是a\[i\]+a\[j\]的可能的方案数，这样，我么就很方便求出了两条边的和的方案数。

但是在加的过程中，我么多加了a\[i\]+a\[i\]的情况，也就是自己跟自己相加的情况，所以我们要减去这一段。而且，在加的过程a\[i\]+a\[j\]和a\[j\]+a\[i\]是同一种情况，我们加了两次，所以要减去一半。

sum是num的前缀和，假设a\[i\]是三角形内要取得最长的边，那么只需要在前面取两条边并且这两条边的和大于a\[i\];  
而长度和大于a\[i\]的取两个的取法是sum\[len\]-sum\[a\[i\]\].

但是这里面有不符合的。  
一个是包含了取一大一小的  
cnt -= (long long)(n-1-i)\*i;  
一个是包含了取一个本身i,然后取其它的  
cnt -= (n-1);  
还有就是取两个都大于的了  
cnt -= (long long)(n-1-i)\*(n-i-2)/2;  
这样把i从0~n-1累加，就答案了。

参考了kuangbin 的博客：  
[http://www.cnblogs.com/kuangbin/archive/2013/07/24/3210565.html][http_www.cnblogs.com_kuangbin_archive_2013_07_24_3210565.html]

code：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    const double PI=acos(-1.0);
    typedef long long ll;
    
    struct complex
    {
        double l,r;
        complex(double ll=0.0,double rr=0.0){
            l=ll;r=rr;
        }
        complex operator +(const complex& B){
            return complex(l+B.l,r+B.r);
        }
        complex operator - (const complex& B){
            return complex(l-B.l,r-B.r);
        }
        complex operator *(const complex& B){
            return complex(l*B.l-r*B.r,l*B.r+B.l*r);
        }
    };
    
    /* * 进行FFT和IFFT前的反转变换。 * 位置i和j（i二进制反转后位置）互换 * len必须是2的幂 */
    void change(complex y[],int len){
        int i,j,k;
        for (int i=1,j=len/2;i<len-1;i++){
            if (i<j) swap(y[i],y[j]);
            k=len/2;
            while (j>=k){
                j-=k;
                k>>=1;
            }
            if (j<k) j+=k;
        }
    }
    /* * 做FFT * len必须为2^k形式， * on==1时是DFT，on==-1时是IDFT */
    void fft(complex y[],int len,int on){
        change(y,len);
        for (int h=2;h<=len;h<<=1){
            complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
            for (int j=0;j<len;j+=h){
                complex w(1,0);
                for (int k=j;k<j+h/2;k++){
                    complex u=y[k];
                    complex t=w*y[k+h/2];
                    y[k]=u+t;
                    y[k+h/2]=u-t;
                    w=w*wn;
                }
            }
        }
        if (on==-1){
            for (int i=0;i<len;i++){
                y[i].l/=len;
            }
        }
    }
    const int MAXN=400040;
    complex x1[MAXN];
    ll sum[MAXN],num[MAXN];
    int a[MAXN/4];
    
    int main()
    {
        int T,n;
        scanf("%d",&T);
        while (T--){
            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,len=1;
            while (len<2*len1) len<<=1;
            for (int i=0;i<len1;i++){
                x1[i]=complex(num[i],0);
            }
            for (int i=len1;i<len;i++){
                x1[i]=complex(0,0);
            }
            fft(x1,len,1);
            for (int i=0;i<len;i++) x1[i]=x1[i]*x1[i];
            fft(x1,len,-1);
            for (int i=0;i<len;i++) {
                num[i]=(ll) (x1[i].l+0.5);
            }
            len=2*a[n-1];
            for (int i=0;i<n;i++) num[a[i]+a[i]]--;
            for (int i=1;i<=len;i++) num[i]/=2;
            sum[0]=0;
            for (int i=1;i<=len;i++) sum[i]=sum[i-1]+num[i];
    
            ll cnt=0;
            for (int i=0;i<n;i++){
                cnt+=sum[len]-sum[a[i]];
                cnt-=(ll)(n-i-1)*i;
                cnt-=(n-1);
                cnt-=(ll) (n-1-i)*(n-i-2)/2;
            }
            ll tot=(ll)n*(n-1)*(n-2)/6;
            printf("%.7f\n",1.0*cnt/tot);
        }
    }

[http_www.cnblogs.com_kuangbin_archive_2013_07_24_3210565.html]: http://www.cnblogs.com/kuangbin/archive/2013/07/24/3210565.html