spoj-TSUM Triple Sums

题目描述

题解：

很吊的容斥+$FFT$，但是并不难。

首先，由于有重复，我们要容斥。

怎么办？

记录三个多项式，

只取一个：$w1$;

相同物体拿两个：$w2$;

相同物体拿三个：$w3$;

然后答案能推出来是$(w1*w1*w1-3*w1*w2+2*w3)/6$;

然后$FFT$瞎搞就行了。

注意有负数，同时扩大再瞎搞。

代码：

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 300000

#define ll long long

const double Pi = acos(-1.0);

template<typename T>

inline void read(T&x)

{

    T f=,c=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){c=c*+ch-'';ch=getchar();}

    x = f*c;

}

struct cp

{

    double x,y;

    cp(){}

    cp(double x,double y):x(x),y(y){}

    cp operator + (const cp &a)const{return cp(x+a.x,y+a.y);}

    cp operator - (const cp &a)const{return cp(x-a.x,y-a.y);}

    cp operator * (const cp &a)const{return cp(x*a.x-y*a.y,x*a.y+y*a.x);}

};

int to[N];

void fft(cp *a,int len,int k)

{

    for(int i=;i<len;i++)

        if(i<to[i])swap(a[i],a[to[i]]);

    for(int i=;i<len;i<<=)

    {

        cp w0(cos(Pi/i),k*sin(Pi/i));

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

        {

            cp w(,);

            for(int o=;o<i;o++,w=w*w0)

            {

                cp w1 = a[j+o],w2 = w*a[j+o+i];

                a[j+o] = w1+w2;

                a[j+o+i] = w1-w2;

            }

        }

    }

    if(k==-)

        for(int i=;i<len;i++)

            a[i].x=(ll)round(a[i].x/len+0.1);

}

int n,a[N],lim=,l;

cp w1[N],w2[N],w3[N],w4[N],w5[N];

int main()

{

//    freopen("tt.in","r",stdin);

    read(n);

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

    {

        read(a[i]);

        a[i]+=;

    }

    while(lim<)lim<<=,l++;

    for(int i=;i<lim;i++)to[i]=((to[i>>]>>)|((i&)<<(l-)));

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

    {

        w1[a[i]].x++;

        w2[a[i]*].x++;

        w3[a[i]*].x++;

    }

    fft(w1,lim,),fft(w2,lim,);

    for(int i=;i<lim;i++)

    {

        w4[i] = w1[i]*w1[i]*w1[i];

        w5[i] = w1[i]*w2[i];

    }

    fft(w4,lim,-),fft(w5,lim,-);

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

    {

        ll tmp = (ll)(w4[i].x-*w5[i].x+*w3[i].x+0.1)/;

        if(tmp)

            printf("%d : %lld\n",i-,tmp);

    }

    return ;

}