题目描述
传送门
题目大意：给定n个长度分别为a_i的木棒，问随机选择3个木棒能够拼成三角形的概率。
题解
三角形的两边之和大于第三边。如果我们直接用这个计算实际上是不好计算的，因为上面的条件中两边必须是较小的两条边。 我们考虑他的补集。然后用总方案-不合法方案。所谓不合法方案就是两边之和小于第三边的。对于所有不合法的三角形，只可能有一种搭配不合法。 例如
a+b<c
，那么一定不可能
b+c<a
表示长度为i的方案数。然后做卷积，得到g[i]表示的是两个线段的长度之和为i的方案数。再从中减去自己选两次的方案，再除以2就是g[i]。 令t[i]表示长度大于等于i的边数。 那么不合法的方案就是
∑mx∗2i=1g[i]∗t[i]
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 500003
#define pi acos(-1)
#define LL long long
using namespace std;
struct data{
double x,y;
data(
double X=
0,
double Y=
0){
x=X,y=Y;
}
}f[N];
data
operator +(data a,data b){
return data(a.x+b.x,a.y+b.y);
}
data
operator -(data a,data b){
return data(a.x-b.x,a.y-b.y);
}
data
operator *(data a,data b)
{
return data(a.x*b.x-a.y*b.y,a.y*b.x+a.x*b.y);
}
int n,T,a[N],L,R[N],n1;
LL g[N],t[N];
void FFT(data a[],
int n,
int opt)
{
for (
int i=
0;i<n;i++)
if (i>R[i]) swap(a[i],a[R[i]]);
for (
int i=
1;i<n;i<<=
1) {
data wn=data(
cos(pi/i),opt*
sin(pi/i));
for (
int p=i<<
1,j=
0;j<n;j+=p) {
data w=data(
1,
0);
for (
int k=
0;k<i;k++,w=w*wn) {
data x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y; a[j+k+i]=x-y;
}
}
}
if (opt==-
1)
for (
int i=
0;i<n;i++) f[i].x/=n;
}
int main()
{
freopen(
"a.in",
"r",stdin);
scanf(
"%d",&T);
while (T--){
scanf(
"%d",&n);
int mx=
0; LL sum=n;
memset(a,
0,
sizeof(a));
memset(g,
0,
sizeof(g));
memset(f,
0,
sizeof(f));
memset(t,
0,
sizeof(t));
for (
int i=
1;i<=n;i++) {
scanf(
"%d",&a[i]); mx=max(mx,a[i]);
g[a[i]*
2]--; f[a[i]].x++; t[a[i]]++;
}
for (
int i=mx;i>=
1;i--) t[i]+=t[i+
1];
mx*=
2; L=
0; sum=sum*(LL)(n-
1)*(LL)(n-
2)/
6;
for (n1=
1;n1<=mx;n1<<=
1) L++;
for (
int i=
0;i<=n1;i++) R[i]=(R[i>>
1]>>
1)|((i&
1)<<(L-
1));
FFT(f,n1,
1);
for (
int i=
0;i<=n1;i++) f[i]=f[i]*f[i];
FFT(f,n1,-
1);
for (
int i=
0;i<=n1;i++) g[i]+=(LL)(f[i].x+
0.5);
LL ans=
0;
for (
int i=
0;i<=n1;i++) ans+=(g[i]/
2)*t[i];
ans=sum-ans;
printf(
"%.7lf\n",(
double)ans*
1.0/sum);
}
}
