3509: [CodeChef] COUNTARI
Time Limit: 40 Sec Memory Limit: 128 MBSubmit: 554 Solved: 148
[Submit][Status][Discuss]
Description
给定一个长度为N的数组A[],求有多少对i, j, k(1<=i<j<k<=N)满足A[k]-A[j]=A[j]-A[i]。
Input
第一行一个整数N(N<=10^5)。
接下来一行N个数A[i](A[i]<=30000)。
Output
一行一个整数。
Sample Input
10
3 5 3 6 3 4 10 4 5 2
Sample Output
9
HINT
听说这道题可以被一种神奇的暴力水过去,而且时间还比正解要来的快。。那我感觉可能是数据比较水。
我来讲讲FFT的做法吧。首先分块,我们分三种情况来考虑,第一种,三个数在同一个块内,直接暴力。第二种,两个数在同一个块内,另一个数不在这个块内,还是直接暴力。第三种,没有两个数在一个块内,那么我们枚举中间的数x,它对答案的贡献就是它左边的块与它右边的块中,和为2*x的数对个数。
我们令这个块的左右端点为l,r,我们把0~l-1这些数类似于基数排序放进a数组中,把r+1~n用同样的方法放进b数组中,那么对于x,它对答案的贡献即为,sigma(a[i]*b[2*x-i]),发现这就是个卷积的形式,用FFT来解决。
至此,本题就可以过了。
代码:
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; struct cp{double x,y;}; double pi=acos(-1); int n,num,len; int w[500010],l[500010],r[500010],sum[500010],sum1[500010]; ll ans; const int m=65536; cp cur[500010],a[500010],b[500010],c[500010]; cp operator *(cp x,cp y){return (cp){x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x};} cp operator +(cp x,cp y){return (cp){x.x+y.x,x.y+y.y};} cp operator -(cp x,cp y){return (cp){x.x-y.x,x.y-y.y};} void fft(cp *a,int n,int fl) { for (int i=n>>1,j=1;j<n;j++) { if (i<j) swap(a[i],a[j]); int k=n>>1; for (;k&i;i^=k,k>>=1);i^=k; } for (int m=2;m<=n;m<<=1) { cp w=(cp){cos(2*pi*fl/m),sin(2*pi*fl/m)}; cur[0]=(cp){1,0}; for (int i=1;i<=m;i++) cur[i]=cur[i-1]*w; for (int i=0;i<n;i+=m) for (int j=i;j<i+(m>>1);j++) { cp u=a[j],v=a[j+(m>>1)]*cur[j-i]; a[j]=u+v; a[j+(m>>1)]=u-v; } } } int main() { scanf("%d",&n); for (int i=0;i<n;i++) scanf("%d",&w[i]); len=(int)sqrt(n*log(n)/log(2));num=n/len;if (n%len) num++; for (int i=1;i<=num;i++){l[i]=(i-1)*len;r[i]=min(l[i]+len-1,n-1);} for (int i=1;i<=num;i++) { for (int j=l[i];j<=r[i];j++) { for (int k=j+1;k<=r[i];k++) if (2*w[j]-w[k]>=0) ans+=(ll)sum1[2*w[j]-w[k]]; sum1[w[j]]++; } } for (int i=num;i>=1;i--) { for (int j=l[i];j<=r[i];j++) for (int k=j+1;k<=r[i];k++) if (2*w[k]-w[j]>=0) ans+=(ll)sum[2*w[k]-w[j]]; for (int j=l[i];j<=r[i];j++) sum[w[j]]++; } for (int i=2;i<num;i++) { for (int j=0;j<m;j++) a[j].x=a[j].y=b[j].x=b[j].y=0; for (int j=0;j<l[i];j++) a[w[j]].x=a[w[j]].x+1; for (int j=r[i]+1;j<n;j++) b[w[j]].x=b[w[j]].x+1; fft(a,m,1);fft(b,m,1); for (int j=0;j<m;j++) c[j]=a[j]*b[j]; fft(c,m,-1); for (int j=0;j<m;j++) c[j].x=(ll)(c[j].x/m+0.5); for (int j=l[i];j<=r[i];j++) ans+=(ll)c[2*w[j]].x; } printf("%lld\n",ans); }