Lvat_s Blog

这题一眼FFT，注意$a_i$的范围也是10W左右(题目没写)

怎么做：构建指数型母函数$F(x)=a_0+a_1*x+...+a_k*x^k$，其中$a_i$是长度为$i$的木棍个数，指数就是长度

那么卷积一次后顺着扫描一遍，边扫描边统计当前有多少种组合情况，注意偶数会多算一倍需要减掉

那么不能组成的概率就是当前的组合种数乘以当前长度的木棍数

最后答案只需要用1减一下就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
 
const int N=262144;
const double Pi=acos(-1);
 
int n,Step,Rev[N],tn,test,nn,Su[N];
 
struct Complex{
double a,b;
Complex(){}
Complex(double sa,double sb){a=sa;b=sb;}
friend Complex operator+(Complex A,Complex B){return Complex(A.a+B.a,A.b+B.b);}
friend Complex operator-(Complex A,Complex B){return Complex(A.a-B.a,A.b-B.b);}
friend Complex operator*(Complex A,Complex B){return Complex(A.a*B.a-A.b*B.b,A.b*B.a+B.b*A.a);}
}A[N];
 
void FFT(Complex *r,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(r[i],r[Rev[i]]);
for(int k=1;k<n;k<<=1){
    Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
    for(int i=0;i<n;i+=k<<1){
        Complex wkj=Complex(1.0,0.0);
        for(int j=0;j<k;j++){
            Complex x=r[i+j],y=r[i+j+k]*wkj;
            r[i+j]=x+y;
            r[i+j+k]=x-y;
            wkj=wkj*wk;
        }
    }
}
if(flag==-1)for(int i=0;i<n;i++)r[i].a/=n;
}
 
int main(){
freopen("3513.in","r",stdin);
freopen("3513.out","w",stdout);
scanf("%d",&test);
while(test--){
    scanf("%d",&tn);nn=0;Rev[0]=0;
    memset(Su,0,sizeof(Su));
    for(int i=1;i<=tn;i++){int x;scanf("%d",&x);Su[x]++;nn=max(x,nn);}
    nn++;
    nn<<=1;
    for(n=1,Step=0;n<nn;n<<=1,Step++);
    nn>>=1;
    for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
    for(int i=0;i<n;i++)A[i]=Complex(Su[i],0.0);
    FFT(A,1);
    for(int i=0;i<n;i++)A[i]=A[i]*A[i];
    FFT(A,-1);
    long long ans=0,tot=1ll*tn*(tn-1)*(tn-2)/6,can=0;
    for(int i=0;i<=nn;i++){
        can+=(long long)(A[i].a+0.5);
        if(!(i%2))can-=Su[i/2];
        if(!Su[i])continue;
        ans+=Su[i]*can;
    }
    ans>>=1;
    printf("%.7lf\n",1.0-1.0*ans/tot);
}
return 0;
}