[BZOJ3771] Triple

題目描述：

霧.

題目分析：

Come from zyf2000

構造多項式.

首先1個的直接統計

将所有的數搞成一個生成函數，做一遍卷積搞出來選2個的答案

但是2個的存在選了兩個相同的，或者選了一個排列，直接除2即可

然後生成函數卷兩次統計選3個的答案

這裡需要容斥一下，(選3個的答案-強行選了2個一樣的*3+強行選了3個一樣的*2)/6才是不考慮順序、選不重複的3個的答案

強行選了3個一樣的直接枚舉，強行選了2個一樣的就将每一個數的兩倍搞成生成函數再和1的卷一下求出

用FFT加速

題目連結：

沒權限号的請點這裡

Ac 代碼：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
const int maxm=;
const double PI=std::acos(-); 
struct complex{
    double real,imag;
    complex(){}; 
    complex(double _real,double _imag):real(_real),imag(_imag){}
}; 
inline complex operator + (complex x,complex y)
{
    return (complex){x.real+y.real,x.imag+y.imag};
}
inline complex operator - (complex x,complex y)
{
    return (complex){x.real-y.real,x.imag-y.imag};
}
inline complex operator * (complex x,complex y)
{
    return (complex){x.real*y.real-x.imag*y.imag,x.real*y.imag+x.imag*y.real};
}
inline complex operator * (complex x,double y)
{
    return (complex){x.real*y,x.imag*y};
}
inline complex operator / (complex x,double y)
{
    return (complex){x.real/y,x.imag/y};
}
complex A[maxm],B[maxm],C[maxm];
int rev[maxm],len;
inline void FFT(complex *a,int n,int f)
{
    for(int i=;i<n;i++) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
    for(int i=;i<n;i<<=)
    {
        complex wn=(complex){std::cos(PI/i),f*std::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=a[i+j+k]*w;
                a[j+k]=x+y,a[i+j+k]=x-y;
            }
        }
    }
    if(f==-) for(int i=;i<n;i++) a[i].real/=n;
}
int n,m,maxi;
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        maxi=std::max(maxi,x);
        A[x].real=B[*x].real=C[*x].real=;
    }
    for(m=;m<=*maxi;m<<=) len++; 
    for(int i=;i<m;i++) rev[i]=((rev[i>>]>>)|((i&)<<(len-)));
    FFT(A,m,),FFT(B,m,),FFT(C,m,);
    for(int i=;i<m;i++)
     A[i]=A[i]+(A[i]*A[i]-B[i])/+(A[i]*A[i]*A[i]-A[i]*B[i]*+C[i]*)/;
    FFT(A,m,-);
    for(int i=;i<m;i++)
     if(round(A[i].real)) printf("%d %d\n",i,(int)round(A[i].real));
    return ;
}