BZOJ 3509 分块FFT

思路：

跟今年WC的题几乎一样 （但是这道题有重 不能用bitset水过去）

正解：分块FFT

http://blog.csdn.net/geotcbrl/article/details/50636401    from GEOTCBRL

可以看看hgr的题解..写得很详细

//By SiriusRen

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const double pi=acos(-);

const int N=;

int n,nn,num[N],R[N],L,Block,block[N],cnt[][N];

long long ans;

struct Complex{

    double x,y;Complex(){}

    Complex(double X,double Y){x=X,y=Y;}

}A[N],B[N],C[N];

Complex operator+(Complex a,Complex b){return Complex(a.x+b.x,a.y+b.y);}

Complex operator-(Complex a,Complex b){return Complex(a.x-b.x,a.y-b.y);}

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

Complex operator/(Complex a,int b){return Complex(a.x/b,a.y/b);}

void FFT(Complex *a,int f){

    for(int i=;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);

    for(int i=;i<n;i<<=){

        Complex wn=Complex(cos(pi/i),f*sin(pi/i));

        for(int j=;j<n;j+=(i<<)){

            Complex w=Complex(,);

            for(int k=;k<i;k++,w=w*wn){

                Complex x=a[j+k],y=w*a[j+k+i];

                a[j+k]=x+y,a[j+k+i]=x-y;

            }

        }

    }

    if(!~f)for(int i=;i<n;i++)a[i]=a[i]/n;

}

int main(){

    scanf("%d",&nn);

    for(int i=;i<=nn;i++)scanf("%d",&num[i]);

    for(n=;n<=;n<<=)L++;

    for(int i=;i<n;i++)R[i]=(R[i>>]>>)|((i&)<<(L-));

    Block=min(int(sqrt(nn)*),nn);

    for(int i=;i<=nn;i++)block[i]=(i-)/Block+;

    for(int i=;i<=nn;i++)cnt[block[i]][num[i]]++;

    for(int I=;I<=block[nn];I++){

        int L=lower_bound(block+,block++nn,I)-block,R=upper_bound(block+,block++nn,I)-block-;

        for(int j=L;j<=R;j++){

            cnt[I][num[j]]--;

            for(int i=L;i<j;i++)

                if(num[j]*-num[i]>=)ans+=cnt[I][num[j]*-num[i]];

        }

    }

    for(int i=;i<=nn;i++)cnt[][num[i]]++;

    for(int I=;I<=block[nn];I++){

        int L=lower_bound(block+,block++nn,I)-block,R=upper_bound(block+,block++nn,I)-block-;

        for(int i=L;i<=R;i++)cnt[][num[i]]--;

        for(int j=L;j<=R;j++)

            for(int i=L;i<j;i++)

                if(num[j]*-num[i]>=)ans+=cnt[][num[j]*-num[i]];

    }

    for(int i=;i<=nn;i++)cnt[][num[i]]++;

    for(int I=block[nn];I;I--){

        int L=lower_bound(block+,block++nn,I)-block,R=upper_bound(block+,block++nn,I)-block-;

        for(int i=L;i<=R;i++)cnt[][num[i]]--;

        for(int k=L;k<=R;k++)

            for(int j=k-;j>=L;j--)

                if(num[j]*-num[k]>=)ans+=cnt[][num[j]*-num[k]];

    }

    for(int I=;I<=block[nn];I++){

        for(int i=;i<n;i++)A[i].x=A[i].y=B[i].x=B[i].y=;

        int L=lower_bound(block+,block++nn,I)-block,R=upper_bound(block+,block++nn,I)-block-;

        for(int i=;i<L;i++)A[num[i]].x++;

        for(int i=R+;i<=nn;i++)B[num[i]].x++;

        FFT(A,),FFT(B,);

        for(int i=;i<n;i++)C[i]=A[i]*B[i];

        FFT(C,-);

        for(int i=L;i<=R;i++)ans+=(long long)(C[num[i]*].x+0.2);

    }

    printf("%lld\n",ans);

}

分块FFT哦~