Lvat_s Blog

这题是FFT的应用

考虑构建指数型母函数，系数是物品的个数，指数是物品的价值

然后分成三种情况容斥一下

然后就不会了。。这怎么FFT啊

然后orz了Miskcoo大神的博客，不仅学会了怎么做，还优化了一下速度……

复数什么的直接无视，和正常的情况一样搞就行了

以后还是要多做题啊……

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;

const int N=262145;
const double Pi=acos(-1);

int An,n,Step,mx_val,Rev[N];

struct Complex{
double a,b;
Complex(){a=0.0,b=0.0;}
Complex(double sa,double sb){a=sa;b=sb;}
friend Complex operator+(Complex A,Complex B){return Complex(A.a+B.a,A.b+B.b);}
friend Complex operator-(Complex A,Complex B){return Complex(A.a-B.a,A.b-B.b);}
friend Complex operator*(Complex A,Complex B){return Complex(A.a*B.a-A.b*B.b,A.a*B.b+A.b*B.a);}
}A[N],B[N],C[N],div2=Complex(1.0/2.0,0.0),div3=Complex(1.0/3.0,0.0),div6=Complex(1.0/6.0,0.0);

void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
	Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
	for(int i=0;i<n;i+=k<<1){
		Complex wkj=Complex(1.0,0.0);
        for(int j=0;j<k;j++){
			Complex a=x[i+j],b=x[i+j+k]*wkj;
			x[i+j]=a+b;
			x[i+j+k]=a-b;
			wkj=wkj*wk;
        }
	}
}
if(flag==-1)for(int i=0;i<n;i++)x[i].a/=n;
}

int main(){
freopen("3771.in","r",stdin);
freopen("3771.out","w",stdout);
scanf("%d",&An);
for(int i=0;i<An;i++){
	int x;
	scanf("%d",&x);
	A[x].a+=1.0;
	B[x*2].a+=1.0;
	C[x*3].a+=1.0;
	if(3*x>mx_val)mx_val=3*x;
}
for(n=1,Step=0;n<mx_val;n<<=1,Step++);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);
FFT(B,1);
for(int i=0;i<n;i++)A[i]=A[i]*A[i]*A[i]*div6+(A[i]*(A[i]-B[i])-B[i])*div2+A[i];
FFT(A,-1);
for(int i=1;i<mx_val;i++)A[i]=A[i]+C[i]*div3;
for(int i=0;i<mx_val;i++){
	int x=(int)(A[i].a+0.5);
	if(x)printf("%d %d\n",i,x);
}
return 0;
}