Lvat_s Blog

先坑着

这两次考试再也不能炸了。毕竟已经炸了NOIP2015,WC2016,AHOI2016,再炸就真GG了

----------------------------------------

并不想写游记了

两场考试全部纸牌回家

还是写写UOJ群聚吧

嗯……看到了VFK好萌哒

还有好多神犇……

完全忝列其中

VFK还向每个人敬了酒(当然不认识我了)

----------------------------------------

热烈祝贺Newnode成为中国国家队队长！

lzz没考好rank6,面试被刷了

也就这么多了吧

这题我写+调了一晚上……代码能力太差

首先忘了LCT怎么维护生成树，看了半天以前的代码

然后写了1.5h。。然后过不了样例

调试

调试

调试

呀！原来这里写错了！改！

样例还是不对……

调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试调试

Splay写错了！改！

样例过了！

提交，AC了！

真心写不动题解了……Claris题解

现在才真正感受到wzf AHOI2016Day1考场写12k+代码AK的可怕……我写调了将近3h，然而这代码4k不到……

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

const int N=200005,INF=2100000000;

int n,m,T,cnt,in[N],on[N];

struct Line{int v;Line *next;Line(int ux=0){v=ux;next=NULL;}}*Sline[N],*Eline[N];
void AddLineS(int u,int v){Line *x=new Line(v);x->next=Sline[u];Sline[u]=x;}
void AddLineE(int u,int v){Line *x=new Line(v);x->next=Eline[u];Eline[u]=x;}

struct Edge{
int u,v,t;
}e[N];

struct Node{
int v,rev,sum,id;
Node *ch[2],*fa,*mne;
Node(){}
Node(int vx,int vy);
void Pushdown();
void Pushup();
}*tree[2*N],*Null;

Node::Node(int val,int vy){
v=val;
id=vy;
sum=id>n;
rev=0;
ch[0]=ch[1]=fa=Null;
mne=this;
}

void Node::Pushdown(){
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
}
}

void Node::Pushup(){
mne=this;
sum=id>n;
if(ch[0]!=Null){if(mne->v>ch[0]->mne->v)mne=ch[0]->mne;sum+=ch[0]->sum;}
if(ch[1]!=Null){if(mne->v>ch[1]->mne->v)mne=ch[1]->mne;sum+=ch[1]->sum;}
}

bool Notroot(Node *x){return x->fa->ch[0]==x || x->fa->ch[1]==x;}
void Prepare(Node *x){if(Notroot(x))Prepare(x->fa);x->Pushdown();}
Node *GetNull(){Node *p=new Node(INF,0);p->v=INF;p->id=p->sum=p->rev=0;p->ch[0]=p->ch[1]=p->fa=p->mne=p;return p;}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}}
void Makeroot(Node *x){Access(x);Splay(x);x->rev^=1;swap(x->ch[0],x->ch[1]);}
void Link(Node *x,Node *y){Makeroot(x);x->fa=y;}
void Cut(Node *x,Node *y){Makeroot(x);Access(y);Splay(y);if(y->ch[0]==x){y->ch[0]=Null;x->fa=Null;}}
Node *Find(Node *x){Access(x);Splay(x);while(x->ch[0]!=Null)x=x->ch[0];return x;}
Node *ToLct(int x){return tree[x];}

void Add(int id){
int u=e[id].u,v=e[id].v;
if(u==v){cnt++;in[id]=1;return;}
if(Find(ToLct(u))!=Find(ToLct(v))){on[id]=1;Link(ToLct(u),ToLct(id+n));Link(ToLct(v),ToLct(id+n));}
else {
	Makeroot(ToLct(u));
	Access(ToLct(v));
	Splay(ToLct(v));
	int idx=ToLct(v)->mne->id-n;
    if(e[idx].t<e[id].t){
		if(ToLct(v)->sum&1^1){in[idx]=1;cnt++;}
		Cut(ToLct(e[idx].u),ToLct(idx+n));Cut(ToLct(e[idx].v),ToLct(idx+n));
		Link(ToLct(u),ToLct(id+n));Link(ToLct(v),ToLct(id+n));
		on[idx]=0;on[id]=1;
    }
    else if(ToLct(v)->sum&1^1){in[id]=1;cnt++;}
}
}

void Del(int id){
if(in[id]){in[id]=0;cnt--;}else if(on[id]){Cut(ToLct(e[id].u),ToLct(id+n));Cut(ToLct(e[id].v),ToLct(id+n));}
}

int main(){
freopen("4025.in","r",stdin);
freopen("4025.out","w",stdout);
scanf("%d %d %d",&n,&m,&T);
Null=GetNull();
for(int i=1;i<=n;i++)tree[i]=new Node(INF,i);
for(int i=1;i<=m;i++){
	int x;
	scanf("%d %d %d %d",&e[i].u,&e[i].v,&x,&e[i].t);
	AddLineS(x,i);
	AddLineE(e[i].t,i);
	tree[i+n]=new Node(e[i].t,i+n);
}
for(int i=0;i<T;i++){
	for(Line *j=Sline[i];j!=NULL;j=j->next)Add(j->v);
	for(Line *j=Eline[i];j!=NULL;j=j->next)Del(j->v);
	puts(cnt?"No":"Yes");
}
return 0;
}

这题真心神题……

首先我们直接考虑第i轮选择谁，那么明显是做不了的，就变成了暴力

我们需要一些独特的DP技巧

首先，我们无视掉m轮的限制，把m次选择全部放在同一轮里面

设$DP[i][j]$为$[i,n]$中的人被选择$j$次的概率

那么显然$DP[0][m]=1$，因为根本没有0号，所以0一定不会被选择

那么转移就变成了

$DP[i][j]=DP[i-1][j]*(1-P[i-1])^j+DP[i-1][j+1]*(1-(1-P[i-1])^{j+1})$

解释:

首先$DP[i-1][j]*(1-P[i-1])^j$表示的是向前面递推到i-1人(因为这一次这一轮没有结束，当前卡牌没有被选择)，同样还是j次机会，上一张卡发动技能的概率是$P[i-1]$(因为上一张卡如果发动了技能就跳到下一轮了),那么不发动技能的概率就是$1-P[i-1]$，j轮不发动技能的概率就是$(1-P[i-1])^j$,前面的$DP[i-1][j]$意思是上一张卡没有发动技能结束回合，这次机会留到这张卡

$DP[i-1][j+1]*(1-(1-P[i-1])^{j+1})$意思是上一张卡在第j轮不幸被选中发动技能了，那么下一次想要选到当前卡牌必须跳到下一轮(所以是$j+1$)，后面的概率意思是上一张卡在前$j+1$轮发动技能的概率(因为直接选中这张卡后会判断当前这张卡有没有发动技能，前面是发动了技能的概率)，那么这次将会跳过这张卡来到当前卡

所以来到当前卡的期望就是上面两者的和

然而答案怎么统计呢?答案因为要统计伤害的期望，那么根据期望的线性性，我们知道第$i$张卡能来到j轮的期望为$DP[i][j]$(来到的意思就是没有在前面发动过技能)

所以$ans=DP[i][j]*(1-(1-P[i])^j)*D[i]$,其中$D[i]$表示的是伤害

怎么找一篇详细的题解那么难。。大部分题解也就两句话，迫使我这样的蒟蒻花很长时间去思考，那些神犇的思维能力太强一句话题解就会做了orzorz

UPD:hzwer的题解比我的好多了。。十分清晰易懂

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

const int N=255;

long double dp[N][N],P[N],D[N],ans;
int n,m,T;

long double Qpow(long double x,int y){
long double ans=1.0;
while(y){
	if(y&1)ans=ans*x;
	x*=x;
	y>>=1;
}
return ans;
}

int main(){
freopen("4008.in","r",stdin);
freopen("4008.out","w",stdout);
scanf("%d",&T);
while(T--){
    scanf("%d %d",&n,&m);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
		double x,y;
		scanf("%lf %lf",&x,&y);
		P[i]=x;D[i]=y;
    }
    dp[0][m]=1.0;
    ans=0.0;
    for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=dp[i-1][j]*Qpow(1-P[i-1],j)+dp[i-1][j+1]*(1-Qpow(1-P[i-1],j+1));
			ans+=dp[i][j]*(1-Qpow(1-P[i],j))*D[i];
		}
    }
    printf("%.10lf\n",(double)ans);
}
return 0;
}

简单的期望DP

分三种情况考虑就可以了

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

const int N=300005;

int n;
double F[N],D[N];
char s[N];

int main(){
freopen("3450.in","r",stdin);
freopen("3450.out","w",stdout);
scanf("%d %s",&n,s+1);
for(int i=1;i<=n;i++){
    if(s[i]=='o'){F[i]=F[i-1]+D[i-1]*2+1;D[i]=D[i-1]+1;}
    if(s[i]=='x'){F[i]=F[i-1];D[i]=0;}
    if(s[i]=='?'){F[i]=F[i-1]+(D[i-1]*2+1)/2;D[i]=(D[i-1]+1)/2;}
}
printf("%.4lf\n",F[n]);
return 0;
}

这题是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;
}

考虑暴力求解

先枚举第一个点，把剩下的点全部扔到一个数组里面

然后极角排序，每次选择一个点和之前枚举的点作为这两个三角形中的两个点，然后乘法计数原理就可以了

注意需要对上面和下面各做一遍(因为两个点上下都有可能)

注意这样做会出现重复，具体就是枚举两个点重复一次和中间计算时上下各计算一次一共四次重复，所以总答案除以4就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
 
const int N=3005;
const double Pi=acos(-1);
 
int n,Top,cnt[2][3],test[N];
long long ans;
 
struct Point{
int x,y;
Point(){}
Point(int sa,int sb){x=sa;y=sb;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
}O;
 
double Atan(Point A){double x=atan2(A.y,A.x);return x>0?x:x+Pi;}
 
pair<Point,int> poi[N],St[N],St2[N];
pair<double,int> Stab[N];
 
void Cal(int col){
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=Top;i++)Stab[i]=make_pair(Atan(St[i].first-O),i);
sort(Stab+1,Stab+Top+1);
for(int i=1;i<=Top;i++)St2[i]=St[Stab[i].second];
for(int i=1;i<=Top;i++)St[i]=St2[i];
for(int i=1;i<=Top;i++){
    if(St[i].first.y<O.y || St[i].first.y==O.y && St[i].first.x>O.x)cnt[test[i]=0][St[i].second]++;
    else cnt[test[i]=1][St[i].second]++;
}
for(int i=1;i<=Top;i++){
    cnt[test[i]][St[i].second]--;
    int CanDoneFirst=1,CanDoneSecond=1;
    if(col!=0)CanDoneFirst*=cnt[0][0];
    if(col!=1)CanDoneFirst*=cnt[0][1];
    if(col!=2)CanDoneFirst*=cnt[0][2];
    if(St[i].second!=0)CanDoneSecond*=cnt[1][0];
    if(St[i].second!=1)CanDoneSecond*=cnt[1][1];
    if(St[i].second!=2)CanDoneSecond*=cnt[1][2];
    ans+=(long long)CanDoneFirst*CanDoneSecond;
    CanDoneFirst=1,CanDoneSecond=1;
    if(col!=0)CanDoneFirst*=cnt[1][0];
    if(col!=1)CanDoneFirst*=cnt[1][1];
    if(col!=2)CanDoneFirst*=cnt[1][2];
    if(St[i].second!=0)CanDoneSecond*=cnt[0][0];
    if(St[i].second!=1)CanDoneSecond*=cnt[0][1];
    if(St[i].second!=2)CanDoneSecond*=cnt[0][2];
    ans+=(long long)CanDoneFirst*CanDoneSecond;
    cnt[test[i]^=1][St[i].second]++;
}
}
 
int main(){
freopen("4246.in","r",stdin);
freopen("4246.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d %d %d",&poi[i].first.x,&poi[i].first.y,&poi[i].second);
}
for(int i=1;i<=n;i++){
    Top=0;
    for(int j=1;j<=n;j++)if(i!=j)St[++Top]=poi[j];
    O=poi[i].first;
    Cal(poi[i].second);
}
printf("%lld\n",ans/4);
return 0;
}

二分+后缀数组

对于height分块然后二分判定就可以了

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

const int N=20005;

int sa[N],rank[N],rank2[N],n,height[N],wa[N],ws[N],a[N],k;

bool cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}

void GetSA(int *r,int *sa,int n,int m){
int i,j,p,*x=rank,*y=rank2,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--){sa[--ws[x[i]]]=i;}
for(j=p=1;p<n;j*=2,m=p){
	for(p=0,i=n-j;i<n;i++)y[p++]=i;
	for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
	for(i=0;i<m;i++)ws[i]=0;
	for(i=0;i<n;i++)ws[wa[i]=x[y[i]]]++;
	for(i=1;i<m;i++)ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--)sa[--ws[wa[i]]]=y[i];
	for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}

void CalHeight(int *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k){
	for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
}

bool Check(int x){
int cnt,i=2;
while(1){
	while(i<=n && height[i]<x)i++;
	if(i>n)break;
	cnt=1;
	while(i<=n && height[i]>=x){cnt++;i++;}
	if(cnt>=k)return 1;
}
return 0;
}

int Div2(){
int l=1,r=n,ans=1;
while(l<=r){
	int mid=l+r>>1;
	if(Check(mid)){ans=mid;l=mid+1;}
	else r=mid-1;
}
return ans;
}

int main(){
freopen("1717.in","r",stdin);
freopen("1717.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
a[n]=0;
GetSA(a,sa,n+1,N-4);
CalHeight(a,sa,n);
printf("%d\n",Div2());
return 0;
}

简单的单调栈

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

int n,Stack[250005],Top,ans;

int main(){
freopen("1113.in","r",stdin);
freopen("1113.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
	int x,y;
	scanf("%d %d",&x,&y);
	while(Top && Stack[Top]>=y){if(Stack[Top]!=y)ans++;Top--;}
	Stack[++Top]=y;
}
printf("%d\n",ans+Top);
return 0;
}

树上分块

对于每个子树维护siz

大于B就把这个子树和当前的省作为一块丢掉（这一块一定小于2*B,否则一定会在这个子树的内部再分块）

最后剩下的点在下面找一个子树丢进去就行了,必定满足条件

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

const int N=2005;

int n,B,en,h[N],St[N],belong[N],St_size,siz[N],home[N],hcnt;

struct Edge{
int b,next;
}e[N];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void DFS(int u,int fa){
St[++St_size]=u;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v==fa)continue;
	DFS(v,u);
	if(siz[u]+siz[v]>=B){
		siz[u]=0;
		home[++hcnt]=u;
		while(St[St_size]!=u)belong[St[St_size--]]=hcnt;
	}
	else siz[u]+=siz[v];
}
siz[u]++;
}

void Paint(int u,int fa,int col){
if(!belong[u])belong[u]=col;
else col=belong[u];
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v!=fa)Paint(v,u,col);
}
}

int main(){
freopen("1086.in","r",stdin);
freopen("1086.out","w",stdout);
scanf("%d %d",&n,&B);
if(n<B){puts("0");return 0;}
for(int i=1;i<n;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdge(u,v);
	AddEdge(v,u);
}
DFS(1,0);
if(!hcnt)home[++hcnt]=1;
Paint(1,0,hcnt);
printf("%d\n",hcnt);
for(int i=1;i<=n;i++)printf("%d ",belong[i]);
putchar('\n');
for(int i=1;i<=hcnt;i++)printf("%d ",home[i]);
putchar('\n');
return 0;
}

把FFT模版略微改动一下

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
 
const int N=270000;
const double Pi=acos(-1);
 
int An,Bn,Cn,n,Rev[N],Step;
 
struct Complex{
double a,b;
Complex(){}
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];
 
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("2194.in","r",stdin);
freopen("2194.out","w",stdout);
scanf("%d",&An);
Bn=An;Cn=An+Bn-1;
for(int i=0;i<An;i++)scanf("%lf %lf",&A[i].a,&B[An-i].a);
for(n=1,Step=0;n<Cn;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++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=Cn/2+1;i<=Cn;i++)printf("%d\n",(int)(C[i].a+0.5));
return 0;
}