【BZOJ 3509】[CodeChef] COUNTARI

解题报告

XeHoTh似乎用一份巨强暴力，卡到了BZOJ和CC的Rank 1

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int M = 70009;
const int N = 100009;
const int T = 15;
const int L = 1 << T + 1;
const double EPS = 0.5;
const double PI = acos(-1);

int n,S,ed,arr[N],tot[M],pos[M];
struct COMPLEX{
double a,b;
inline COMPLEX() {}
inline COMPLEX(double x, double y):a(x),b(y) {}
inline COMPLEX operator - (const COMPLEX &B) {return COMPLEX(a-B.a,b-B.b);}
inline COMPLEX operator + (const COMPLEX &B) {return COMPLEX(a+B.a,b+B.b);}
inline COMPLEX operator * (const COMPLEX &B) {return COMPLEX(a*B.a-b*B.b,a*B.b+b*B.a);}
}a1[M],a2[M],bas(1,0);
LL vout,cnt[M];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void FFT(COMPLEX *a, int T = 1) {
for (int i=0;i<L;i++) if (pos[i]<i) swap(a[pos[i]],a[i]);
for (int l=2;l<=L;l<<=1) {
COMPLEX wn(cos(2*PI/l),sin(2*PI/l)*T),w(1,0);
for (int i=0;i<L;i+=l,w=bas) {
for (int j=i;j<(i+(l>>1));j++,w=w*wn) {
COMPLEX tmp = w * a[j+(l>>1)];
a[j+(l>>1)] = a[j] - tmp;
a[j] = a[j] + tmp;
}
}
}
}

int main() {
n = read(); S = 4000;
for (int i=1;i<=n;i++) arr[i] = read();
for (int i=1;i<L;i++) pos[i] = (pos[i>>1]>>1)|((i&1)<<T);
for (int i=S+1;i+S<=n;i+=S) {
memset(a1,0,sizeof(a1));
memset(a2,0,sizeof(a2));
for (int j=1;j<i;j++) a1[arr[j]] = a1[arr[j]] + bas;
for (int j=i+S;j<=n;j++) a2[arr[j]] = a2[arr[j]] + bas;
FFT(a1); FFT(a2);
for (int j=0;j<L;j++) a1[j] = a1[j] * a2[j];
FFT(a1, -1);
for (int j=0;j<L;j++) cnt[j] = a1[j].a / L + EPS;
for (int j=i;j<i+S;j++) vout += cnt[arr[j]<<1];
}
for (int i=1,t;i<=n;i+=S) {
ed = max(ed, i);
for (int j=i,lim=min(n+1,i+S);j<lim;j++) {
for (int k=j+1;k<lim;k++) {
t = (arr[j] << 1) - arr[k];
vout += t<M&&t>0? tot[t]: 0;
}
tot[arr[j]]++;
}
}
memset(tot,0,sizeof(tot));
for (int i=ed,t;i>0;i-=S) {
for (int j=min(n,i+S-1);j>=i;j--) {
for (int k=j-1;k>=i;k--) {
t = (arr[j] << 1) - arr[k];
vout += t<M&&t>0? tot[t]: 0;
}
}
for (int j=min(n,i+S-1);j>=i;j--) tot[arr[j]]++;
}
printf("%lld\n",vout);
return 0;
}


2 thoughts to “【BZOJ 3509】[CodeChef] COUNTARI”

1. Hey there, You’ve done an excellent job. I’ll definitely digg it and personally suggest to my friends. I am sure they will be benefited from this site.

2. I’m still learning from you, as I’m making my way to the top as well. I definitely enjoy reading all that is written on your blog.Keep the aarticles coming. I enjoyed it!