记录编号	376736	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2015]无聊的会议V2	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	7.337 s
提交时间	2017-02-28 06:40:49	内存使用	24.13 MiB

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<cmath>
#include<ctime>
using namespace std;
#define	fcl	fclose(stdin);	fclose(stdout);	return 0
	#define SUBMIT 2333
const int maxn=1048576+10;
const double PI=2*acos(-1.0);
struct Complex{
	double a,b;
	Complex(){a=b=0;}
	Complex(const double& x,const double& y){a=x; b=y;}
	inline Complex operator * (const Complex& x)const{return Complex(a*x.a-b*x.b,a*x.b+b*x.a);}
	inline void operator += (const Complex& x){a+=x.a; b+=x.b;}
	inline Complex operator - (const Complex& x)const{return Complex(a-x.a,b-x.b);}
	inline void operator *= (const double& x){a*=x; b*=x;}
	inline void operator *= (const Complex& x){
		double q=a*x.a-b*x.b,p=a*x.b+b*x.a;
		a=q; b=p;
	}
}A[maxn],w,wn;
int Rev[maxn];
int ans[500010];
int n,N,K;
inline void REV(){
	for(N=1,K=0;N<(n<<1);N<<=1,++K); --K;
	for(int i=0;i<N;++i) Rev[i]=((Rev[i>>1]>>1)|((i&1)<<K));
}
int ch[500010];
inline void Read(int& x){while(x=getchar(),x<'0'||x>'9'); x-='0';}
char CH[100]; int LL;
inline void Print(int x){
	if(!x) puts("0");
	else{
		for(LL=0;x;x/=10) CH[++LL]=x%10+'0';
		for(;LL;--LL) putchar(CH[LL]);
		puts("");
	}
}
inline void FFT(Complex* Q,const int& M,const int& Ty){
	int l,i,k,c;
	for(i=0;i<M;++i) if(Rev[i]<i) swap(Q[Rev[i]],Q[i]);
	for(l=2,c=1;l<=M;c=l,l<<=1){
		wn=Complex(cos(PI*Ty/l),sin(PI*Ty/l));
		for(i=0;i<M;i+=l){
			w.a=1; w.b=0;
			for(k=i;k<(c+i);++k,w*=wn){
				Complex *y=&Q[k];
				Complex x=w*(*(y+c));  (*(y+c))=(*y)-x; (*y)+=x;
			}
		}
	}
	if(Ty==-1){
		double Inv=1.0/M;	for(int i=0;i<M;++i) Q[i]*=Inv;
	}
}
bool flag[100]={false};
int main(){
	#ifdef SUBMIT
	freopen("OXO.in","r",stdin);
	freopen("OXO.out","w",stdout);
	#endif
	scanf("%d",&n);
	for(int i=0;i<n;++i){
		Read(ch[i]);
		flag[ch[i]]=true;
	}
	REV();
	for(int k=0,i;k<5;++k){
		if(!flag[k]) continue;
		for(i=0;i<n;++i){
			if(ch[i]==k) A[i].a=1.0;
			else A[i].a=0;
			A[i].b=0;
		}
		for(i=n;i<N;++i) A[i].a=A[i].b=0;
		FFT(A,N,1);
		for(i=0;i<N;++i) A[i]*=A[i];
		FFT(A,N,-1);
		for(i=0;i<n;++i) if(ch[i]==k) ans[i]+=((A[i<<1].a-1)+0.5);
	}
	for(int i=0;i<n;++i) Print(ans[i]>>1);
	#ifndef SUBMIT
	getchar(); getchar();
	#endif
	fcl;
}