Submission #1679455

---

Source Code Expand

#include<bits/stdc++.h>
#define mo 924844033ll
using namespace std;
long long a[800010],b[800010],c[800010],ym[800010],fac[200010],nifac[200010];
vector<int> des[200010];
int n;
int getmi(int a,int x)
{
	int ans=1;
	while (x)
	{
		if (x&1) ans=(long long)ans*a%mo;
		a=(long long)a*a%mo;
		x>>=1;
	}
	return ans;
}
long long C(int n,int m)
{
	if ((n<0)||(m<0)||(n<m)) return 0;
	return (long long)fac[n]*nifac[m]%mo*nifac[n-m]%mo;
}
int dfs(int s,int pre=0)
{
	int ans=1;
	for (int k=0;k<des[s].size();k++) if (des[s][k]!=pre) ans+=dfs(des[s][k],s);
	if (pre) {a[ans]++;a[n-ans]++;}
	return ans;
}
void fft(long long a[],int n)
{
	if (n==1) return;
	long long l[n>>1],r[n>>1];
	for (int i=0;i<(n>>1);i++)
	{
		l[i]=a[i<<1];
		r[i]=a[(i<<1)+1];
	}
	fft(l,n>>1);fft(r,n>>1);
	long long wn=ym[n],w=1;
	for (int i=0;i<(n>>1);i++)
	{
		a[i]=(l[i]+w*r[i])%mo;
		a[i+(n>>1)]=(l[i]-w*r[i])%mo;
		w=w*wn%mo;
	}
}
int main()
{
	scanf("%d",&n);
	fac[0]=nifac[0]=1;
	for (int i=1;i<=n;i++)
	{
		fac[i]=(long long)fac[i-1]*i%mo;
		nifac[i]=getmi(fac[i],mo-2);
	}
	if (fac[n]*nifac[n]%mo!=1) assert(0);
	for (int i=1;i<n;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		des[u].push_back(v);des[v].push_back(u);
	}
	dfs(1);
	for (int i=0;i<=n;i++)
	{
		a[i]=(long long)a[i]*fac[i]%mo;
		c[i]=nifac[n-i];
	}
	//for (int i=0;i<=2*n;i++) cout<<i<<' '<<a[i]<<' '<<c[i]<<endl;
	/*for (int i=0;i<=n;i++)
	for (int j=0;j<=2*n;j++)
		b[i+j]=(b[i+j]+a[i]*c[j])%mo;*/
	//for (int i=0;i<=3*n;i++) cout<<i<<' '<<b[i]<<endl;
	//for (int i=1;i<=n;i++) printf("%lld\n",(mo-b[i+n]*nifac[i]%mo+n*C(n-1,i-1)+n*C(n-1,i))%mo);
	
	int mi=1;while (mi<=3*n+10) mi<<=1;
	for (int i=1;i<=mi;i<<=1) ym[i]=getmi(5,(mo-1)/i);
	fft(a,mi);fft(c,mi);
	for (int i=0;i<mi;i++) a[i]=a[i]*c[i]%mo;
	fft(a,mi);
	for (int i=1;i<(mi>>1);i++) swap(a[i],a[mi-i]);
	int ni=getmi(mi,mo-2);
	for (int i=0;i<mi;i++) a[i]=a[i]*ni%mo;
	for (int i=0;i<mi;i++) a[i]+=mo;
	//for (int i=0;i<=n;i++) cout<<a[i+n]*nifac[i]%mo<<endl;
	for (int i=1;i<=n;i++) printf("%lld\n",(mo-a[i+n]*nifac[i]%mo+n*C(n-1,i-1)+n*C(n-1,i))%mo);
	/*for (int i=1;i<=n;i++)
	{
		int ans=(n*C(n-1,i-1)+n*C(n-1,i))%mo;
		for (int j=0;j<=n;j++)
		{
			ans-=(a[j]+b[j])*C(j,i);
		}
		cout<<(ans%mo+mo)%mo<<endl;
	}*/
}

Submission Info

Compile Error

./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:60:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int u,v;scanf("%d%d",&u,&v);
                              ^

Judge Result