# 题面

for k<-0 to n do
ans <- 该 k 情况下的答案
print ans


# 题目分析

$k$要取遍，并且是 $10^5$级的数据，考虑 FFT。

# 代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int q=0,w=1;char ch=' ';
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
return q*w;
}
typedef long long LL;
typedef double db;
const db pi=3.1415926535897384626;
const int N=524300;
struct com{db r,i;}a[N],b[N];
int n,X,tot,len,kn;
int sum[N],rev[N];LL ans[N];
com operator* (com a,com b) {return (com){a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r};}
com operator- (com a,com b) {return (com){a.r-b.r,a.i-b.i};}
com operator+ (com a,com b) {return (com){a.r+b.r,a.i+b.i};}
com operator/ (com a,db b) {return (com){a.r/b,a.i/b};}
void NTT(com *a,int n,int x) {
for(RI i=0;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
for(RI i=1;i<n;i<<=1) {
com wn=(com){cos(pi/i),sin(pi/i)*x};
for(RI j=0;j<n;j+=(i<<1)) {
com t1,t2,w=(com){1,0};
for(RI k=0;k<i;++k,w=w*wn)
t1=a[j+k],t2=w*a[j+i+k],a[j+k]=t1+t2,a[j+i+k]=t1-t2;
}
}
if(x==-1) for(RI i=0;i<n;++i) a[i]=a[i]/(db)n;
}
int main()
{
for(RI i=1;i<=n;++i) ++a[sum[i-1]].r;
for(RI i=1;i<=n;++i) ++b[sum[n]-sum[i]].r;
kn=1;while(kn<=sum[n]*2) kn<<=1,++len;
for(RI i=1;i<kn;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
NTT(a,kn,1),NTT(b,kn,1);
for(RI i=0;i<kn;++i) a[i]=a[i]*b[i];
NTT(a,kn,-1);
int js=0;
for(RI i=1;i<=n;++i)
if(sum[i]==sum[i-1]) ++js;
else ans[0]+=1LL*js*(js-1)/2+js,js=0;
ans[0]+=1LL*js*(js-1)/2+js;
for(RI i=0;i<sum[n];++i) ans[sum[n]-i]=(LL)(a[i].r+0.2);
for(RI i=0;i<=n;++i) printf("%lld ",ans[i]);
puts("");
return 0;
}