F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 3513 >> 求助
gmh77 @ 2018-06-21 18:59:48
[ Quote ] [ Edit ] [ Delete ] 1#
如题,我写的程序比网上的标程快N倍,但在bzoj上TLE了
是不是有什么奇怪的操作,还是我写错了某些地方
向dalao求助,已交八十多次

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define max(a,b) (a>b?a:b)
#define pi 6.283185307179586476925286766559
#define Len 10
#define MaxN 262144
using namespace std;

//__attribute__((optimize("-O2")))
inline int getint() { char c; int ret=0; for(c=getchar(); c<'0' || c>'9'; c=getchar()); for(; c>='0'&&c<='9'; c=getchar()) ret=ret*10+c-'0'; return ret; }

struct C{
double a,b;
// C (double _a=0,double _b=0) {a=_a,b=_b;}
};

//C operator+(C x,C y) {return C(x.a+y.a , x.b+y.b);}
//C operator-(C x,C y) {return C(x.a-y.a , x.b-y.b);}
//C operator*(C x,C y) {return C(x.a*y.a-x.b*y.b , x.a*y.b+x.b*y.a);}

int num[Len][MaxN];
C a[Len][2][MaxN];
C AA[MaxN];
int c[MaxN];
long long ans[MaxN];
double Cos[21];
double Sin[21];
long long n,i,j,k,l,L,N,len,T,mx,tt,Mod;
double s1,s2;
double _s,sum,all,Ans;
long double X1,Y1,X2,Y2;

int s,S,S2;
C u,v,w,W,_w;

//__attribute__((optimize("-O2")))
void init()
{
// memset(num,0,sizeof(num));
// memset(a,0,sizeof(a));
// memset(b,0,sizeof(b));

mx=0;
n=getint();
fo(i,1,n) j=getint(),num[T][j]++,a[T][0][j].a++,a[T][1][j].a++,mx=max(mx,j);

// len=ceil(log(100000)/log(2))+1;
len=ceil(log(mx)/log(2))+1;
N=pow(2,len);

fo(i,0,N-1)
{
j=i;
k=0;

fo(l,1,len)
{
k=(k<<1)+(j&1);
j>>=1;
}

c[k]=i;
}
}

//__attribute__((optimize("-O2")))
void fft(/*register*/ int type,int size)
{
fo(i,0,N-1) AA[i]=a[T][size][c[i]];
fo(i,0,N-1) a[T][size][i]=AA[i];

s=N;
S=1;

fo(i,1,len)
{
S2=S;
s>>=1;S<<=1;

// w=C(1,0);
w.a=1;
w.b=0;

// C W(Cos[S2+1] , Sin[S2+1]*type);
// W.a=cos(pi/S);
// W.b=sin(pi/S*type);
W.a=Cos[i];
W.b=Sin[i]*type;

fo(j,0,S2-1)
{
l=j,L=j+S2;

// w.a=Cos[S2+j];
// w.b=Sin[S2+j]*type;

// w.a-=0.000000000001;
// w.b-=0.000000000000001;
// if (abs(Cos[S2+j]-w.a)>0.000000000001) cout<<"FaQ"<<endl;
// if (abs(Sin[S2+j]*type-w.b)>0.000000000001) cout<<"FaQ"<<endl;

fo(k,0,s-1)
{
u=a[T][size][l];
// v=w*a[T][size][L];
v.a=w.a*a[T][size][L].a-w.b*a[T][size][L].b;
v.b=w.a*a[T][size][L].b+w.b*a[T][size][L].a;

// a[T][size][l]=u+v;
// a[T][size][L]=u-v;

a[T][size][l].a=u.a+v.a;
a[T][size][l].b=u.b+v.b;
a[T][size][L].a=u.a-v.a;
a[T][size][L].b=u.b-v.b;

l+=S;L+=S;
}

X1=w.a,Y1=W.a,X2=w.b,Y2=W.b;

// _w=w;
// w.a=_w.a*W.a-_w.b*W.b;
// w.b=_w.a*W.b+_w.b*W.a;
w.a=X1*Y1-X2*Y2;
w.b=X1*Y2+X2*Y1;
// w=w*W;
}
}
}

//__attribute__((optimize("-O2")))
int main()
{

k=1;
fo(i,1,18)
{
k<<=1;
Cos[i]=cos(pi/k);
Sin[i]=sin(pi/k);
}

Mod=tt%Len;
T=Mod;
for (tt=getint(); tt; tt--)
{
init();
if (n<3) {printf("0.0000000\n");continue;}

fft(1,0);fft(1,1);

fo(i,0,N-1)
{
s1=a[T][0][i].a,s2=a[T][0][i].b;
a[T][0][i].a=s1*a[T][1][i].a-s2*a[T][1][i].b;
a[T][0][i].b=s1*a[T][1][i].b+s2*a[T][1][i].a;
}
// a[T][0][i]=a[T][0][i]*a[T][1][i];

fft(-1,0);

fo(i,0,N-1)
ans[i]=floor(a[T][0][i].a+0.5)/N;

fo(i,0,N-1)
if (ans[i])
{
if (!(i&1))
ans[i]-=num[T][i>>1];
ans[i]>>=1;
}

sum=0;_s=0;
fd(i,N-1,1)
{
_s+=num[T][i];
Ans=ans[i];
sum+=Ans*_s;
}

all=(double)n;
all=all*(all-1)*(all-2)/6.0;

printf("%.7lf\n",1.0-((double)sum/(double)all));

if (tt>1)
{
T=(T+Len-1)%Len;
if (T==Mod)
{
memset(a,0,sizeof(a));
memset(num,0,sizeof(num));
}
}
}
}
gmh77 @ 2018-06-22 12:21:29
[ Quote ] [ Edit ] [ Delete ] 2#
是不是跑太快会超时

在线等
Cydiater @ 2018-06-22 14:45:18
[ Quote ] [ Edit ] [ Delete ] 3#
跑太快会被+1s,当然会超时啦
[Top] [Previous Page] [Next Page]

HOME Back