网站平台多少钱,wordpress主题受损,做网站的职业规划,网站建设项目报告统计每种长度的木棒数量#xff0c;先计算出两根棒子能构成的长度#xff0c;想到卷积。1.拿这个序列卷积自己 2.计算重算的部分#xff0c;首先是一条边自己和自己的这种情况#xff0c;另一种是(i,j)和(j,i)这种形式。第一种#xff0c;可以枚举读入的木棒长度#xff… 统计每种长度的木棒数量先计算出两根棒子能构成的长度想到卷积。1.拿这个序列卷积自己 2.计算重算的部分首先是一条边自己和自己的这种情况另一种是(i,j)和(j,i)这种形式。第一种可以枚举读入的木棒长度再长度为其二倍的位置-1第二种在第一种处理完之后直接除2。计算出两根棒子能构成的长度后我们枚举最长的那条边答案一定在长度大于它的里面但是要去掉算了自己的情况和存在一条边大于最长边的情况。具体公式看代码。这题中间精度差了些就挂了。可以用long long就不要用double。 #include bits/stdc.h
#define pi acos(-1.0)
const int maxn 3000005;
using namespace std;
typedef long long ll;
struct E{double real,imag;E(double real0,double imag0):real(real),imag(imag){}friend E operator (E A,E B){return E(A.realB.real,A.imagB.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.realA.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 i0;in;i)if(irev[i])swap(a[i],a[rev[i]]);for(int i1;in;i1){E wnE(cos(pi/i),ty*sin(pi/i));for(int p(i1),j0;jn;jp){E w(1,0);for(int k0;ki;k,ww*wn){E xa[jk],yw*a[jki];a[jk]xy;a[jki]x-y;}}}if(ty-1)for(int i0;in;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); L0;memset(c,0,sizeof(c));memset(e,0,sizeof(e));memset(rev,0,sizeof(rev));memset(F,0,sizeof(F));for(int i1;in;i) {scanf(%lld,e[i]);F[e[i]];mx max(mx,e[i]);}m mx*2;for(mx1;mxm;mx1)L;for(int i0;imx;i)rev[i](rev[i1]1)|((i1)(L-1));for(int i0;imx;i)c[i]F[i];fft(c,1,mx);for(int i0;imx;i) c[i]c[i]*c[i];fft(c,-1,mx);for(int i0;imx;i)b[i] (ll)(c[i].real0.5);for(int i1;in;i) --b[e[i]1];for(int i0;imx;i) b[i]1;for(int i1;imx;i) b[i]b[i-1];sort(e1,e1n);ll ans 0;for(int i1;in;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
