Submission #1690864

---

Source Code Expand

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

using namespace std;

const int N=8e5+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 BRC(int *y,int len)
{
	for (int i=0;i<len;++i) 
		if (R[i]<i) swap(y[i],y[R[i]]);
}

void ntt(int *y,int len,int f)
{
	BRC(y,len);
	fprintf(stderr,"%d\n",clock());
	for (int h=2;h<=len;h<<=1)
	{
		int wn=qpow(5,(Mod-1)/h);
		if (f==-1) wn=qpow(wn,Mod-2);
		for (int j=0;j<len;j+=h)
		{
			int w=1;
			for (int k=j;k<j+h/2;++k)
			{
				int u=y[k],t=1ll*w*y[k+h/2]%Mod;
				y[k]=(u+t)%Mod;
				y[k+h/2]=(u-t+Mod)%Mod;
				w=1ll*w*wn%Mod;
			}
		}
	}
    if(f==-1){
        int ny=qpow(len,Mod-2);
        for(int i=0;i<len;i++) 
			y[i]=1ll*y[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 len,L=0; for (len=1;len<((n+1)<<1);len<<=1) ++L;
    for(int i=0;i<len;i++)R[i]=R[i>>1]>>1|((i&1)<<(L-1));
	ntt(P,len,1); ntt(B,len,1); 
    for(int i=0;i<len;i++)F[i]=1ll*P[i]*B[i]%Mod;
//    for (int i=0;i<len;++i) printf("%d%c",F[i],i==len-1?'\n':' ');
    ntt(F,len,-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 ntt(int*, int, int)’:
./Main.cpp:77:31: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘clock_t {aka long int}’ [-Wformat=]
  fprintf(stderr,"%d\n",clock());
                               ^
./Main.cpp: In function ‘void Init()’:
./Main.cpp:19:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:23: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