統計每種長度的木棒數量，先計算出兩根棒子能構成的長度，想到卷積。1.拿這個序列卷積自己 2.計算重算的部分，首先是一條邊自己和自己的這種情況，另一種是(i,j)和(j,i)這種形式。第一種，可以枚舉讀入的木棒長度，再長度為其二倍的位置-1；第二種，在第一種處理完之后，直接除2。計算出兩根棒子能構成的長度后，我們枚舉最長的那條邊，答案一定在長度大于它的里面，但是要去掉算了自己的情況，和存在一條邊大于最長邊的情況。具體公式看代碼。這題中間精度差了些就掛了。可以用long long就不要用double。

#include <bits/stdc++.h> #define pi acos(-1.0) const int maxn = 300000+5; using namespace std; typedef long long ll; struct E{double real,imag;E(double real=0,double imag=0):real(real),imag(imag){}friend E operator +(E A,E B){return E(A.real+B.real,A.imag+B.imag);}friend E operator -(E A,E B){return E(A.real-B.real,A.imag-B.imag);}friend E operator *(E A,E B){return E(A.real*B.real-A.imag*B.imag,A.imag*B.real+A.real*B.imag);} }; int n,m,mx,L,rev[maxn]; E f[maxn],rf[maxn],g[maxn],e1[maxn],e2[maxn]; void fft(E *a,int ty,int n){for(int i=0;i<n;++i)if(i<rev[i])swap(a[i],a[rev[i]]);for(int i=1;i<n;i<<=1){E wn=E(cos(pi/i),ty*sin(pi/i));for(int p=(i<<1),j=0;j<n;j+=p){E w(1,0);for(int k=0;k<i;++k,w=w*wn){E x=a[j+k],y=w*a[j+k+i];a[j+k]=x+y;a[j+k+i]=x-y;}}}if(ty==-1)for(int i=0;i<n;++i)a[i].real/=n; } E c[maxn]; int T; ll e[maxn],F[maxn],b[maxn]; int main() {scanf("%d",&T);while(T--) {ll mx = 0;scanf("%lld",&n); L=0;memset(c,0,sizeof(c));memset(e,0,sizeof(e));memset(rev,0,sizeof(rev));memset(F,0,sizeof(F));for(int i=1;i<=n;++i) {scanf("%lld",&e[i]);++F[e[i]];mx = max(mx,e[i]);}m = mx*2;for(mx=1;mx<=m;mx<<=1)++L;for(int i=0;i<mx;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));for(int i=0;i<mx;++i)c[i]=F[i];fft(c,1,mx);for(int i=0;i<mx;++i) c[i]=c[i]*c[i];fft(c,-1,mx);for(int i=0;i<mx;++i)b[i] = (ll)(c[i].real+0.5);for(int i=1;i<=n;++i) --b[e[i]<<1];for(int i=0;i<mx;++i) b[i]>>=1;for(int i=1;i<mx;++i) b[i]+=b[i-1];sort(e+1,e+1+n);ll ans = 0;for(int i=1;i<=n;++i){ans = ans + (ll)(b[mx-1]-b[e[i]]);ans -= (ll)(n-1LL);ans -= (ll)(n-i)*(i-1);ans -= (ll)(n-i)*(n-i-1LL)/2LL;}ll t = 1LL*n*(n-1LL)*(n-2LL)/6LL;printf("%.7f\n",1.0*ans/t);} }

　　

轉載于:https://www.cnblogs.com/RRRR-wys/p/8967563.html

總結

以上是生活随笔為你收集整理的BZOJ 3513: [MUTC2013]idiots [FFT]的全部內容，希望文章能夠幫你解決所遇到的問題。

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