【FFT】HDU4609 3-idiots

分析:

要求的就是$A_x+A_y-A_z\leq 0$的方案数
只要$x≠y$,就能保证如果满足条件，则选择一定合法（即$x≠y,y≠z,x≠z$）

所以只需要令$A_x$表示$x$出现的次数，然后求出$A^2$

设一多项式$B_x$表示$\frac x 2$出现的次数

$A^2-B$即为所有选$x、y$的合法方案。
所以再求一个前缀和，对每个值$a_i$求$A^2-B$中不大于$a_i$项的系数和，累加就是答案。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 300010
#define MOD 1004535809
typedef long long ll;
const int G=3;
const int siz=262144;
using namespace std;
const double Pi=acos(-1);
struct cpx{double r,i;cpx() {}cpx(double _r,double _i):r(_r),i(_i) {}cpx operator * (const cpx &a) const{return cpx(r*a.r-i*a.i,r*a.i+i*a.r);}cpx operator + (const cpx &a) const{return cpx(r+a.r,i+a.i);}cpx operator - (const cpx &a) const{return cpx(r-a.r,i-a.i);}
};
void fft(cpx *a,int f,int N){int i,j,k;for(i=1,j=0;i<N;i++){for(int d=N;j^=d>>=1,~j&d;);if(i<j)swap(a[i],a[j]);}for(i=1;i<N;i<<=1){cpx wn(cos(Pi/i),f*sin(Pi/i));for(j=0;j<N;j+=i<<1){cpx w(1,0);for(k=0;k<i;k++,w=w*wn){cpx x=a[j+k],y=w*a[i+j+k];a[j+k]=x+y;a[i+j+k]=x-y;}}}if(f==-1)for(i=0;i<N;i++)a[i].r/=N;
}
cpx A[MAXN];
int t[100010],ts;
ll s[100010],n;
int main(){SF("%d",&ts);while(ts--){memset(A,0,sizeof A);SF("%I64d",&n);for(int i=0;i<n;i++){SF("%d",&t[i]);A[t[i]].r++;}fft(A,1,siz);for(int i=0;i<=siz;i++)A[i]=A[i]*A[i];fft(A,-1,siz);for(int i=0;i<n;i++)A[t[i]*2].r--;for(int i=0;i<=100000;i++)s[i]=(long long)(A[i].r+0.5)/2ll;for(int i=1;i<=100000;i++)s[i]+=s[i-1];ll sum=n*(n-1ll)*(n-2ll)/6ll;for(int i=0;i<n;i++)sum-=s[t[i]];ll tot=n*(n-1ll)*(n-2ll)/6ll;PF("%.7lf\n",(1.0*sum)/(1.0*tot));}
}