BZOJ3771 : Triple （生成函数+FFT+容斥）

本文主要是介绍BZOJ3771 : Triple （生成函数+FFT+容斥），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
大概就是构造分别取一个，两个，三个，三种的生成函数
然后乘的时候肯定有算重的
就容斥就好了
代码里有式子：（rank24，有点儿小开心）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define LL long long
using namespace std;
inline int read(){int x=0,f=1;char ch=' ';while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
const int N=2e5+5;
const double pi=acos(-1);
struct cp{double r,i;cp(){}cp(double _r,double _i):r(_r),i(_i){}inline cp operator + (const cp& b) const {return cp(r+b.r,i+b.i);}inline cp operator - (const cp& b) const {return cp(r-b.r,i-b.i);}inline cp operator * (const cp& b) const {return cp(r*b.r-i*b.i,r*b.i+i*b.r);}inline cp operator * (double b) {return cp(r*b,i*b);}inline cp operator / (double b) {return cp(r/b,i/b);}
}A[N],B[N],C[N];
int n,Ai,mx,m,L,R[N],ans[N];
inline void FFT(cp *a,int n,int f){for(int i=0;i<n;++i)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));for(int i=0;i<n;++i)if(i<R[i])swap(a[i],a[R[i]]);for(int i=1;i<n;i<<=1){cp wn(cos(pi/i),f*sin(pi/i));for(int j=0;j<n;j+=(i<<1)){cp w(1,0);for(int k=0;k<i;++k,w=w*wn){cp x=a[j+k],y=w*a[j+k+i];a[j+k]=x+y;a[j+k+i]=x-y;}}}if(f==-1)for(int i=0;i<n;++i)a[i].r/=n;
}
int main(){n=read();for(int i=1;i<=n;++i){Ai=read();A[Ai]=cp(1,0);B[2*Ai]=cp(1,0);C[3*Ai]=cp(1,0);mx=max(mx,Ai);}m=mx*3;for(n=1;n<m;n<<=1)L++;FFT(A,n,1);FFT(B,n,1);FFT(C,n,1);for(int i=0;i<n;++i)A[i]=A[i]+(A[i]*A[i]-B[i])/2.0+(A[i]*A[i]*A[i]-A[i]*B[i]*3.0+C[i]*2.0)/6.0;FFT(A,n,-1);for(int i=0;i<n;++i)ans[i]=(int)(A[i].r+0.5);for(int i=0;i<n;++i)if(ans[i])printf("%d %d\n",i,ans[i]);return 0;
}