Submission #1796622

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(a,b,c) for (int a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
#define go(u) for (int o=ft[u],v;v=E[o].t;o=E[o].n)
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> par;
//const int P=998244353,G=3,iG=332748118,N=530010;
const LL P=924844033,G=5,iG=554906420,N=530010;
int n,tot;
struct edge{int t,n;}E[N<<1];
LL a[N],b[N],c[N],d[N],inv[N],s1[N],s2[N],ft[N],s[N],cnt[N];
LL w[N],_f[N],_g[N],*f=_f,*g=_g;
void dft(LL *a,LL n,LL w0){
	w[0]=1;
	rep(i,1,n-1) w[i]=w[i-1]*w0%P;
	memcpy(f,a,sizeof(b));
	LL i=1,j,k=0;
	for (;i;k++,swap(f,g)) for (i=0;i<n>>k+1;i++) for (j=0;j<1<<k;j++)
		g[i<<k+1|j]		=(f[i<<k|j]+w[n*j>>k+1]*f[i<<k|j|n>>1])%P,
		g[i<<k+1|j|1<<k]=(f[i<<k|j]-w[n*j>>k+1]*f[i<<k|j|n>>1])%P;
	memcpy(a,g,sizeof(b));
}
void add(int x,int y){
	E[++tot]=(edge){y,ft[x]},ft[x]=tot;
}
void dfs(int u,int f=0){
	go(u) if (v!=f){
		dfs(v,u);
		s[u]+=s[v];
	}
	++s[u];
	go(u) if (v!=f) ++cnt[s[v]];
	++cnt[n-s[u]];
}
LL pw(LL x,LL k){
	LL y=1;
	while (k){
		if (k&1) y=y*x%P;
		k>>=1;
		x=x*x%P;
	}
	return y;
}
int main(){
	scanf("%d",&n);
	rep(i,2,n){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1);
	LL len=n*2+10;
	while (1){
		len+=len&-len;
		if (len==(len&-len)) break;
	}
	inv[1]=s1[0]=s2[0]=1;
	rep(i,2,n) inv[i]=inv[P%i]*(P-P/i)%P;
	rep(i,1,n) s1[i]=s1[i-1]*i%P,s2[i]=s2[i-1]*inv[i]%P;
	rep(i,0,n) a[i]=cnt[i]*s1[i]%P;
	rep(i,0,n) b[i]=s2[n-i];
//	len=8;
	rep(i,0,len-1) rep(j,0,len-1) d[(i+j)%len]=(d[(i+j)%len]+a[i]*b[j])%P;
	dft(a,len,pw(G,(P-1)/len));
	dft(b,len,pw(G,(P-1)/len));
	rep(i,0,len-1) c[i]=a[i]*b[i]%P;
	dft(c,len,pw(iG,(P-1)/len));
	LL invlen=pw(len,P-2);
	rep(i,0,len-1) c[i]=c[i]*invlen%P;
	rep(i,1,n){
		LL ans=s1[n]*s2[i]%P*s2[n-i]%P*n%P;
		ans=(ans-c[i+n]*s2[i])%P;
		ans=(ans+P)%P;
		printf("%lld\n",ans);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void add(int, int)’:
./Main.cpp:29:24: warning: narrowing conversion of ‘ft[x]’ from ‘LL {aka long long int}’ to ‘int’ inside { } [-Wnarrowing]
  E[++tot]=(edge){y,ft[x]},ft[x]=tot;
                        ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:50:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:53:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
                      ^

Judge Result