直接上代碼

#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; double pi = acos(-1.0); struct complex{double re,im;complex(double r = 0.0,double i = 0.0):re(r),im(i){};complex operator+(complex com){return complex(re+com.re,im+com.im);}complex operator-(complex com){return complex(re-com.re,im-com.im);}complex operator*(complex com){return complex(re*com.re-im*com.im,re*com.im+im*com.re);} }; complex wn,wntmp; void rader(complex arr[],int n){int num = n-1;for(int i = 0;i < n;++i){int tn = n>>1;while(num && num >= tn) num ^= tn,tn >>= 1;num |= tn;if(num > i) swap(arr[i],arr[num]);} } void FFT(complex cs[],int n,int f){rader(cs,n);for(int s = 1;s < n;s <<= 1){wn = complex(cos(f*2*pi/(s*2)),sin(f*2*pi/(s*2)));for(int offset = 0;offset < n;offset += s<<1){wntmp = complex(1.0,0.0);for(int i = 0;i < s;++i){complex u = cs[offset+i],v = cs[offset+i+s]*wntmp;cs[offset+i] = u + v;cs[offset+i+s] = u - v;wntmp = wntmp * wn;}}}if(f == -1)for(int i = 0;i < n;++i)cs[i].re /= n; } const int maxn = 1e5+7; int n; long long ival[maxn<<2]; long long sum[maxn<<2]; complex val[maxn<<2]; long long ord[maxn<<2]; int main(){int T;scanf("%d",&T);while(T--){memset(val,0,sizeof(val));memset(ival,0,sizeof(ival));memset(sum,0,sizeof(sum));scanf("%d",&n);for(int i = 0;i < n;++i){int tmp;scanf("%d",&tmp);ord[i] = tmp;val[tmp].re++;ival[tmp] ++;}sort(ord,ord+n);int len = 1;while(len < ord[n-1]+1) len <<= 1;len <<= 1;FFT(val,len,1);for(int i = 0;i < len; ++i) val[i] = val[i]*val[i];FFT(val,len,-1);for(int i = 1;i < len+1;i++){if(i % 2 == 0) val[i].re = (val[i].re - ival[i/2]);val[i].re /= 2;}for(int i = 1;i < len+1;++i){ival[i] = (long long)(val[i].re+0.5);sum[i] = sum[i-1] + ival[i];}//sum[i]表示的是不重復，和<=i 的種類數//此時ival[i]表示的是兩根不相同的棒棒組合在一起，長度和為i的種類數。long long ans = 0;for(int i = 0;i < n;++i){ans += sum[len] - sum[ord[i]] - (n-1) - (long long)(n-i-1)*(n-i-2)/2 - (long long)(i)*(n-i-1);}double fenmu = double(n)*(n-1)*(n-2)/6;printf("%.7lf\n",double(ans)/fenmu);} return 0; }

總結

以上是生活随笔為你收集整理的hdu4609 3idiots 三角形计数 FFT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。