BZOJ 3513 [MUTC2013]idiots

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3513

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

显然可以用生成函数记录每种长度的出现次数。生成函数自己对自己做多项式乘法即选择两个的方案，注意此处有选择两个自己的重复情况。

由于是等概率取，答案乘一个 C(n,3)，统计不同方案数即可。

一次取两个，只要大于等于这两个的和的都不合法，前缀和统计即可。

学习了一个迭代版 fft...

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 300010
#define ll long long
using namespace std;
inline int read() 
{ 
    int x=0,f=1;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 
    return x*f; 
}
struct cp
{
    double x,y;
    cp(double X=0,double Y=0)
    {
        x=X,y=Y;
    }
};
cp operator +(cp a,cp b){return cp(a.x+b.x,a.y+b.y);}
cp operator -(cp a,cp b){return cp(a.x-b.x,a.y-b.y);}
cp operator *(cp a,cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
cp a[N];
int T;
int n,f[N],Mx,lim,sum[N],r[N],L;
ll dp[N];
void fft(cp *a,int n,int flag)
{
    for(int i=0;i<n;i++) 
    if(r[i]>i)swap(a[i],a[r[i]]);
     
    for(int i=1;i<n;i<<=1) 
    {
        cp w_n(cos(M_PI/i),flag*sin(M_PI/i));
        for(int j=0;j<n;j+=i<<1) 
        {
            cp w(1,0);
            for(int k=0;k<i;k++) 
            {
                cp x=a[j+k],y=w*a[j+k+i];
                a[j+k]=x+y,a[j+k+i]=x-y;
                w=w*w_n;
            }
        }
    }
}
int main()
{
    T=read();
    while(T--)
    {
        L=0;
        memset(f,0,sizeof(f));
        memset(sum,0,sizeof(sum));
        memset(r,0,sizeof(r));
        Mx=0;
        n=read();
        for(int i=1;i<=n;i++)
        {
            int tmp=read();
            f[tmp]++,a[tmp].x++;
            Mx=max(Mx,tmp);
        }
        for(int i=Mx;i>=1;i--)
        sum[i]=sum[i+1]+f[i];
        Mx<<=1;
        for(lim=1;lim<=Mx;lim<<=1)L++;
        for(int i=0;i<=lim;i++) 
        r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
         
        fft(a,lim,1);
        for(int i=0;i<=lim;i++)
        a[i]=a[i]*a[i];
        fft(a,lim,-1);
         
        for(int i=0;i<=lim;i++)
        {
            dp[i]=(ll)(a[i].x/lim+0.5);
            if(!(i&1))
            dp[i]-=f[i>>1];
            dp[i]>>=1;
        }
        double ansa,ansb;
        ansa=ansb=(ll)n*(n-1)*(n-2)/6;
        for(int i=0;i<=lim;i++)
        ansa-=dp[i]*(ll)sum[i];
        for(int i=0;i<=lim;i++)
        a[i].x=a[i].y=0;
        printf("%.7lf\n",ansa/ansb);
 
    }
}

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 300010

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

struct cp

{

double x,y;

cp(double X=0,double Y=0)

{

x=X,y=Y;

}

};

cp operator +(cp a,cp b){return cp(a.x+b.x,a.y+b.y);}

cp operator -(cp a,cp b){return cp(a.x-b.x,a.y-b.y);}

cp operator *(cp a,cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

cp a[N];

int T;

int n,f[N],Mx,lim,sum[N],r[N],L;

ll dp[N];

void fft(cp *a,int n,int flag)

{

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

if(r[i]>i)swap(a[i],a[r[i]]);

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

{

cp w_n(cos(M_PI/i),flag*sin(M_PI/i));

for(int j=0;j<n;j+=i<<1)

{

cp w(1,0);

for(int k=0;k<i;k++)

{

cp x=a[j+k],y=w*a[j+k+i];

a[j+k]=x+y,a[j+k+i]=x-y;

w=w*w_n;

}

int main()

{

T=read();

while(T--)

{

L=0;

memset(f,0,sizeof(f));

memset(sum,0,sizeof(sum));

memset(r,0,sizeof(r));

Mx=0;

n=read();

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

{

int tmp=read();

f[tmp]++,a[tmp].x++;

Mx=max(Mx,tmp);

}

for(int i=Mx;i>=1;i--)

sum[i]=sum[i+1]+f[i];

Mx<<=1;

for(lim=1;lim<=Mx;lim<<=1)L++;

for(int i=0;i<=lim;i++)

r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));

fft(a,lim,1);

for(int i=0;i<=lim;i++)

a[i]=a[i]*a[i];

fft(a,lim,-1);

for(int i=0;i<=lim;i++)

{

dp[i]=(ll)(a[i].x/lim+0.5);

if(!(i&1))

dp[i]-=f[i>>1];

dp[i]>>=1;

}

double ansa,ansb;

ansa=ansb=(ll)n*(n-1)*(n-2)/6;

for(int i=0;i<=lim;i++)

ansa-=dp[i]*(ll)sum[i];

for(int i=0;i<=lim;i++)

a[i].x=a[i].y=0;

printf("%.7lf\n",ansa/ansb);

}

zgz233

BZOJ 3513 [MUTC2013]idiots

BZOJ 1050 [HAOI2006] 旅行 comf

BZOJ 3527 [Zjoi2014] 力

l1ll5

Comments | NOTHING

zgz233