Submission #1679644

---

Source Code Expand

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=924844033;
struct Combin{
	#define N 400005
	int fac[N],rv[N],facrv[N];
	Combin(){
		fac[0]=rv[1]=facrv[0]=1;
		for(int i=2;i<N;i++) rv[i]=((-(LL)(mod/i)*rv[mod%i]%mod)+mod)%mod;
		for(int i=1;i<N;i++) fac[i]=(LL)fac[i-1]*i%mod;
		for(int i=1;i<N;i++) facrv[i]=(LL)facrv[i-1]*rv[i]%mod;
	}
	int C(int r1,int n1){
		if(r1>n1) return 0;
		return fac[n1]*(LL)facrv[r1]%mod*facrv[n1-r1]%mod;
	}
	#undef N
}C;

namespace NTT{
	#define N ((1<<19)+3)
	const int base=5;
	int wn[N+N];
	int rv[N];
	int len;
	int fastpow(int w,int x){
		int ret=1;
		while(x){
			if(x&1) ret=ret*1LL*w%mod;
			w=w*1LL*w%mod;x>>=1;
		}
		return ret;
	}
	void NTT(int *x,int len,int f){
		for(int i=0;i<len;i++) if(i<rv[i]) swap(x[i],x[rv[i]]);
		for(int i=2,d=(len>>1)*f;i<=len;i<<=1,d/=2){
			for(int j=0;j<len;j+=i){
				int *x1=x+j,*x2=x+j+(i>>1),*w=wn+N;long long t1;
				for(int p=0,t=i>>1;p<t;p++,w+=d){
					x2[p]=(x1[p]-(t1=(1LL*x2[p]*(*w))))%mod;
					x1[p]=(x1[p]+t1)%mod;
				}
			}
		}
	}
	
	void pre(int tot){//最终项数（最大次数+1） 
		len=1;while((1<<len)<tot) len++;
		for(int i=1;i<(1<<len);i++) rv[i]=(rv[i>>1]>>1)|((i&1)<<(len-1));
		wn[N]=1;int w=fastpow(base,(mod-1)>>len);len=1<<len;int rv=fastpow(w,mod-2);
		for(int i=1;i<len;i++) wn[N+i]=(1LL*wn[N+i-1]*w)%mod;
		for(int i=N-1;i>=N-len;i--) wn[i]=(1LL*wn[i+1]*rv)%mod;
	}
	void solve(int *a,int *b){
		NTT(a,len,1);NTT(b,len,1);
		for(int i=0;i<len;i++) a[i]=(1LL*a[i]*b[i])%mod;
		NTT(a,len,-1);
		int rl=fastpow(len,mod-2);
		for(int i=0;i<len;i++) a[i]=((a[i]*1LL*rl)%mod+mod)%mod;
	}
}

#define M 200005
struct edge{
	int t,next;
}e[M*2];int ecnt,head[M];
void addedge(int f,int t){
	e[++ecnt]=(edge){t,head[f]};head[f]=ecnt;
	e[++ecnt]=(edge){f,head[t]};head[t]=ecnt;
}
int ai[N],bi[N],ci[M];
int DFS(int u,int fr){
	int sz=1;
	for(int i=head[u];i;i=e[i].next){
		if(e[i].t!=fr)
			sz+=DFS(e[i].t,u);
	}
	if(u!=1) ci[sz]++;
	return sz;
} 
int n;

int ans[M];
int main(){
	scanf("%d",&n);
	for(int i=1,f,t;i<n;i++){
		scanf("%d%d",&f,&t);
		addedge(f,t);
	}
	DFS(1,0);
	for(int i=0;i<=n;i++){
		ans[i]=n*1LL*C.C(i,n)%mod;
		ai[i]=ci[i]*1LL*C.fac[i]%mod;
		bi[n+1-i]=C.facrv[i];
	}
	NTT::pre(n+n+1);
	NTT::solve(ai,bi);
	for(int i=1;i<=n;i++)
		ans[i]=(ans[i]-ai[n+i+1]*1LL*C.facrv[i])%mod; 
	memset(ai,0,sizeof(ai));
	memset(bi,0,sizeof(bi));
	for(int i=0;i<=n;i++){
		ai[i]=ci[i]*1LL*C.fac[n-i]%mod;
		bi[i]=C.facrv[i];
	} 
	NTT::solve(ai,bi);
	for(int i=1;i<=n;i++)
		ans[i]=(ans[i]-ai[n-i]*1LL*C.facrv[i])%mod;
	for(int i=1;i<=n;i++)
		printf("%d\n",(ans[i]+mod)%mod);
} 

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:86:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:88:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&f,&t);
                      ^

Judge Result