BZOJ 3771 Triple ——FFT

直接暴力卷积+统计就可以了。

去重比较复杂。

其实也不复杂，抄吧！

反正AC了。

#include <map>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define ll long long

#define mp make_pair

#define maxn 400005

const double pi=acos(-1.0);

struct Complex{

    double x,y;

    Complex(){}

    Complex(double _x,double _y){x=_x;y=_y;}

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

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

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

}x[maxn],y[maxn],z[maxn],ans3[maxn],ans2[maxn],c[maxn],ans1[maxn],ans[maxn];

int n,a[maxn],mx=0,m=1,len,rev[maxn];

void FFT(Complex * x,int n,int flag)

{

    F(i,0,n-1) if (rev[i]>i) swap(x[i],x[rev[i]]);

    for (int m=2;m<=n;m<<=1)

    {

        Complex wn=Complex(cos(2*pi/m),flag*sin(2*pi/m));

        for (int i=0;i<n;i+=m)

        {

            Complex w=Complex(1.0,0);

            for (int j=0;j<(m>>1);++j)

            {

                Complex u=x[i+j],v=x[i+j+(m>>1)]*w;

                x[i+j]=u+v; x[i+j+(m>>1)]=u-v;

                w=w*wn;

            }

        }

    }

}

int main()

{

    scanf("%d",&n);

    F(i,1,n)

    {

        scanf("%d",&a[i]);

        x[a[i]].x+=1;

        y[a[i]*2].x+=1;

        z[a[i]*3].x+=1;

        mx=max(mx,a[i]);

    }

    n=mx*3+5;while (m<=n) m<<=1,len++; n=m;

    F(i,0,n-1)

    {

        int ret=0,t=i;

        F(j,1,len) ret<<=1,ret|=t&1,t>>=1;

        rev[i]=ret;

    }

    FFT(x,n,1); FFT(y,n,1); FFT(z,n,1);

    F(i,0,n-1) c[i]=x[i]*x[i]*x[i];

    FFT(c,n,-1); F(i,0,n-1) ans3[i].x+=c[i].x/n;

    F(i,0,n-1) c[i]=x[i]*y[i];

    FFT(c,n,-1); F(i,0,n-1) ans3[i].x-=3*c[i].x/n;

    F(i,0,n-1) c[i]=z[i];

    FFT(c,n,-1); F(i,0,n-1) ans3[i].x+=2*c[i].x/n;

    F(i,0,n-1) ans3[i].x=(ans3[i].x+0.3)/6;

    F(i,0,n-1) c[i]=x[i]*x[i];

    FFT(c,n,-1); F(i,0,n-1) ans2[i].x+=c[i].x/n;

    F(i,0,n-1) c[i]=y[i];

    FFT(c,n,-1); F(i,0,n-1) ans2[i].x-=c[i].x/n;

    F(i,0,n-1) ans2[i].x=(ans2[i].x+0.3)/2;

    F(i,0,n-1) c[i]=x[i];

    FFT(c,n,-1); F(i,0,n-1) ans1[i].x+=c[i].x/n;

    F(i,0,n-1) ans[i].x=ans2[i].x+ans3[i].x+ans1[i].x;

    F(i,0,n-1) if ((int)ans[i].x>0) printf("%d %d\n",i,(int)ans[i].x);

}