记录编号	362896	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2015]无聊的会议V2	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	34.326 s
提交时间	2017-01-09 13:59:20	内存使用	59.03 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double db;
const int N=1.1e6+10;
const db pi=acos(-1.0);
#define rint register int
int n,size,a[N],ans[N];
bool vis[5];
struct comp{
	db x,y;
	comp(db X=0,db Y=0){x=X;y=Y;}
	comp operator + (const comp a)const{return comp(x+a.x,y+a.y);}
	comp operator - (const comp a)const{return comp(x-a.x,y-a.y);}
	comp operator * (const comp a)const{return comp(x*a.x-y*a.y,x*a.y+y*a.x);}
}w[N],x[N],tmp[N];
void fft(comp *a,int n,int start,int step){
	if (n==1) return;
	rint m=n>>1;
	fft(a,m,start,step<<1);
	fft(a,m,start+step,step<<1);
	for (rint i=0,pos;i<m;++i){
		pos=2*i*step;
		tmp[i]=a[start+pos]+w[i*step]*a[start+pos+step];
		tmp[i+m]=a[start+pos]-w[i*step]*a[start+pos+step];
	}
	for (rint i=0,p=start;i<n;++i,p+=step) a[p]=tmp[i];
}
void solve(int flag){
	for (int i=0;i<size;i++)
		x[i].y=0,x[i].x=(a[i]==flag);
	fft(x,size,0,1);
	for (int i=0;i<size;i++) x[i]=x[i]*x[i];
	reverse(w,w+size+1);
	fft(x,size,0,1);
	for (int i=0;i<size;i++){
		x[i].x/=size;
		if (!(i&1)&&a[i/2]==flag)
			ans[i>>1]+=int(x[i].x+0.5)>>1;
	}
	reverse(w,w+size+1);
}
int main()
{
	freopen("OXO.in","r",stdin);
	freopen("OXO.out","w",stdout);
	scanf("%d",&n);
	for (int i=0;i<n;i++)
		scanf("%d",&a[i]),vis[a[i]]=1;
	for (size=1;size<n*2;size<<=1);
	for (int i=n;i<size;i++) a[i]=-1;
	w[0]=comp(1,0);
	w[1]=comp(cos(2*pi/size),sin(2*pi/size));
	for (int i=2;i<=size;i++)
		w[i]=w[i-1]*w[1];
	for (int x=0;x<5;x++)
		if (vis[x]) solve(x);
	for (int i=0;i<n;i++)
		printf("%d\n",ans[i]);
	return 0;
}