BZOJ3771 Triple

Description

link

给定 (n) 种物品，每个有不同的价值，可以取 (1,2,3) 个，求不同的价值和每种价值对应的方案

(n le 40000)

Solution

其实是个计数题，还不是那么好入手的计数题

定义 (A[i]=[x=i],B[i]=[2 imes x=i],C[i]=[3 imes x=i])

然后如果取两个进行求价值，那么就是 (A imes A)

（不是卷积……是直接乘法）

三个求价值方案就是(A^3)

显然不对……

因为每种物品都有重复的，所以要去重……

所以两种物品的价值方案是 (frac {A^2-B} 2)

三种就是(frac {A^3-3 imes A imes B +2 imes C} {3!=6})

额挺显然的容斥，然后就上 (FFT) 做乘法就好了

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k=='-') f=-1;
		while(isdigit(k)) res=res*10+k-'0',k=getchar();
		return res*f;
	}
	const int N=15e4+10;
	struct node{
		double x,y;
		node(){}
		node(double xx,double yy){x=xx; y=yy; return ;}
		node operator +(const node a){return node(x+a.x,y+a.y);}
		node operator -(const node a){return node(x-a.x,y-a.y);}
		node operator *(const node a){return node(x*a.x-y*a.y,y*a.x+x*a.y);}
		node operator /(const double a){return node(x/a,y/a);}
		node operator *(const double b){return node(x*b,y*b);}
	}A[N<<2],B[N<<2],C[N<<2];
	int n,m,r[N];
	const double pi=acos(-1);
	inline void fft(node *f,int n,int opt)
	{	
		for(int i=0;i<n;++i) if(i<r[i]) swap(f[i],f[r[i]]);
		for(int p=2;p<=n;p<<=1)
		{
			int len=p>>1; node tmp(cos(pi/len),opt*sin(pi/len));
			for(int k=0;k<n;k+=p)
			{
				node buf(1,0);
				for(int l=k;l<k+len;++l)
				{
					node tt=buf*f[l+len]; 
					f[len+l]=f[l]-tt; f[l]=f[l]+tt;
					buf=buf*tmp;
				}
			}
		}
		if(opt==-1) for(int i=0;i<n;++i) f[i].x/=n;
		return ;
	}
	int maxx,a[N],t;
	signed main()
	{
		t=n=read(); for(int i=1;i<=n;++i) a[i]=read(),A[a[i]].x++,B[a[i]*2].x++,C[a[i]*3].x++;
		int m=a[n]*3; n=1; while(n<=m) n<<=1;
		for(int i=0;i<n;++i) r[i]=r[i>>1]>>1|((i&1)?(n>>1):0);
		
		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]-A[i]*B[i]*3+C[i]*2)/6+(A[i]*A[i]-B[i])/2+A[i];
		fft(A,n,-1); for(int i=0;i<=3*a[t];++i) if((int)(A[i].x+0.5)) printf("%lld %lld
",i,(int)(A[i].x+0.5));  
		return 0;
	}
}
signed main(){return yspm::main();}