Submission #1689596

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <algorithm>
#define Pi acos(-1.0)

using namespace std;

const int N=2e5+10,Mod=924844033;

struct Edge{ int to,next;} way[N<<1];

int n,num[N],tot,A[N],B[N],P[N],F[N<<4],fact[N],fact_inv[N];

void Build(int a,int b) { way[++tot]=(Edge){b,num[a]}; num[a]=tot; }

void Init()
{
	scanf("%d",&n);
	int a,b;
	for (int i=2;i<=n;++i)
	{
		scanf("%d%d",&a,&b);
		Build(a,b); Build(b,a);
	}
}

int son[N];
void Dfs(int x,int fa)
{
	son[x]=1;
	for (int i=num[x];i;i=way[i].next)
	{
		int v=way[i].to;
		if (v==fa) continue;
		Dfs(v,x);
		son[x]+=son[v];
		A[son[v]]--;
	}
	if (n-son[x]) A[n-son[x]]--;
}

int R[N<<2],L;
int inv(int x)
{
	int t=Mod-2,ret=1;
	while (t)
	{
		if (t&1) ret=1ll*ret*x%Mod;
		x=1ll*x*x%Mod;
		t>>=1;
	}
	return ret;
}

int qpow(int x,int k)
{
	int ret=1;
	while (k)
	{
		if (k&1) ret=1ll*ret*x%Mod;
		x=1ll*x*x%Mod;
		k>>=1;
	}
	return ret;
}

void ntt(int *a,int f){
    for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);
    for(int i=1;i<n;i<<=1){
        int gn=qpow(5,(Mod-1)/(i<<1));
        for(int j=0;j<n;j+=i<<1){
            int g=1;
            for(int k=0;k<i;k++,g=1ll*g*gn%Mod){
                int x=a[j+k],y=1ll*g*a[j+k+i]%Mod;
                a[j+k]=(x+y)%Mod;
                a[j+k+i]=(x-y+Mod)%Mod;
            }
        }
    }
    if(f==-1){
        reverse(a+1,a+n);
        int ny=qpow(n,Mod-2);
        for(int i=0;i<n;i++)a[i]=1ll*a[i]*ny%Mod;
    }
}

void Solve()
{
	Dfs(1,0);A[n]=n; 
	fact[0]=1; for (int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%Mod;
	int ny=inv(fact[n]);fact_inv[n]=ny;
	for (int i=n-1;i;--i) fact_inv[i]=1ll*fact_inv[i+1]*(i+1)%Mod;
	fact_inv[0]=1;
	for (int i=0;i<=n;++i) B[i]=fact_inv[i];
	for (int i=0;i<=n;++i) A[i]=1ll*(A[i]+Mod)*fact[i]%Mod;
	for (int i=0;i<=n;++i) P[i]=A[n-i];
	
    int m=n,_n=n;
    for(n=1;n<=m<<1;n<<=1) L++;
    for(int i=0;i<n;i++)R[i]=R[i>>1]>>1|((i&1)<<(L-1));
	ntt(P,1); ntt(B,1); 
    for(int i=0;i<n;i++)F[i]=1ll*P[i]*B[i]%Mod;
    ntt(F,-1);
	for (int i=_n-1;i>=0;--i) 
		printf("%lld\n",1ll*F[i]*fact_inv[_n-i]%Mod);
}

int main()
{
	Init();
	Solve();
	return 0;
}

Submission Info

Compile Error

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

Judge Result