bzoj3513

给定n个长度分别为$a_i$的木棒，问随机选择3个木棒能够拼成三角形的概率。

$a_i$和$n$都在$10^5$以内

对于每一个i，我们统计比i短的边有多少组合能组成长度<=i的

用1减去这个概率就是能拼成的概率

具体就是用sum[i]表示i出现的次数

sum[i]可以转化成如下卷积的样子

$$sum[i] = \sum_{j=1}^{i-1}sum[j] * sum[i - j - 1]$$

然后FFT

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int maxn = ;

const double pi = acos(-1.0);

struct Cint

{

    double r,i;

    Cint() {r = i = 0.00;}

    Cint(double _r,double _i) : r(_r),i(_i){}

    Cint operator + (const Cint &b)const{return Cint(r + b.r,i + b.i);}

    Cint operator - (const Cint &b)const{return Cint(r - b.r,i - b.i);}

    Cint operator * (const Cint &b)const{return Cint(r * b.r - i * b.i,i * b.r + r * b.i);}

}s[maxn];

int a[maxn],LEN,n;

LL sum[maxn],ans;

inline void FFT_init(Cint *a,int len)

{

    for(int i = ,j = len >> ,k;i < len - ;i++)

    {

        if(i < j)swap(a[i],a[j]);k = len;

        while(j >= (k>>=)) j -= k;

        if(j <= k) j += k;

    }

}

inline void FFT(Cint *a,int len,int f)

{

    FFT_init(a,len);int l,i,j,k;Cint u,v;

    for(l = ;l <= len;l <<= )

    {

        i = l >> ;

        Cint w(cos(-f *  * pi / l),sin(-f *  * pi / l));

        for(j = ;j ^ len;j += l)

        {

            Cint wn(1.0,0.0);

            for(k = j;k ^ (i + j);k++)

            {

                u = a[k]; v = wn * a[i + k];

                a[k] = u + v;a[k + i] = u - v;

                wn = w * wn;

            }

        }

    }

    if(f == -)

        for(i = ;i < len;i++)a[i] . r /= len;

}

int main()

{

    //freopen("ou.txt","r",stdin);

    //freopen("x.txt","w",stdout);

    int T;scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);int mx = ;ans = ;

        for(int i=;i<=LEN + ;i++)s[i] = Cint(0.0,0.0);

        for(int i=;i<=n;i++)

        {

            scanf("%d",&a[i]);

            mx = max(mx,a[i]);

        }

        for(LEN = ;(LEN >> ) < mx;LEN <<= );

        for(int i=;i<=n;i++)s[a[i]].r += 1.0;

        FFT(s,LEN,);

        for(int i=;i<LEN;i++)s[i] = s[i] * s[i];

        FFT(s,LEN,-);

        for(int i=;i<=n;i++)s[a[i] * ].r -= 1.0;

        for(int i=;i<=LEN;i++)sum[i] = sum[i-] + floor(s[i].r + 0.5);

        for(int i=;i<=n;i++)ans += sum[a[i]];

        double pos = 3.0 * ans / n / (n - ) / (n - );

        printf("%.7lf\n",1.0 - pos);

    }

}

巴特西

bzoj3513

最新文章

热门文章