Submission #907163

---

Source Code Expand

#include<bits/stdc++.h>
#define N (1<<19)
#define Q 924844033
using namespace std;
inline int qp(int a,int p){
	int r=1;
	while(p){
		if(p&1) r=1LL*a*r%Q;
		a=1LL*a*a%Q;
		p>>=1;
	}
	return r;
}
inline int inv(int x){
	return qp(x,Q-2);
}
int ans[N],cnt[N],sz[N],n,fac[N],ifac[N],fa[N],fb[N],fc[N];
int rt[30],irt[30];
vector<int> g[N];
int build_sz(int u,int p){
	sz[u]=1;
	int tmp=n-1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==p) continue;
		sz[u]+=build_sz(v,u);
		cnt[sz[v]]--;
		if(cnt[sz[v]]<0) cnt[sz[v]]+=Q;
		tmp-=sz[v];
	}
	cnt[tmp]--;
	if(cnt[tmp]<0) cnt[tmp]+=Q;
	return sz[u];
}
void FFT(int x[], bool pos){
    for (int i=1, j=0; i<N; ++i){
        for (int k=N>>1; !((j^=k)&k); k>>=1) ;
        if (i>j) swap(x[i], x[j]);
    }
    for (int k=2; k<=N; k<<=1){
        long long om = pos?rt[__lg(k)]:irt[__lg(k)];
        for (int j=0; j<N; j+=k){
            long long mul = 1;
            for (int i=j; i<j+k/2; i++){
				int a = x[i], b = 1LL*x[i+k/2]*mul%Q;
                x[i]     = (a + b)%Q;
                x[i+k/2] = (a + Q - b)%Q;
                mul = mul*om%Q;
            }
        }
    }
}
void mul(int a[],int b[],int c[]){
	FFT(a,true);
	FFT(b,true);
	for(int i=0;i<N;i++){
		c[i]=1LL*a[i]*b[i]%Q;
	}
	FFT(c,false);
	int iN=inv(N);
	for(int i=0;i<N;i++){
		c[i]=1LL*iN*c[i]%Q;
	}
}
int main(){
	int a,b;
	scanf("%d",&n);
	fac[0]=ifac[0]=1;
	for(int i=1;i<=n;i++){
		fac[i]=1LL*fac[i-1]*i%Q;
		ifac[i]=1LL*ifac[i-1]*inv(i)%Q;
	}
	bool flag=true;
	for(int gn=2;flag;gn++){
		int tmp=qp(gn,441);
		flag=false;
		for(int j=0;j<21;j++){
			rt[21-j]=tmp;
			if(tmp==1){
				flag=true;
				break;
			}
			tmp=1LL*tmp*tmp%Q;
		}
	}
	for(int j=1;j<=21;j++) irt[j]=inv(rt[j]);
	cnt[n]=n;
	for(int i=0;i<n-1;i++){
		scanf("%d%d",&a,&b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	build_sz(1,0);
	for(int i=0;i<=n;i++){
		fa[n-i]=1LL*cnt[i]*fac[i]%Q;
	}
	for(int i=0;i<=n;i++){
		fb[i]=ifac[i];
	}
	mul(fa,fb,fc);
	for(int i=1;i<=n;i++){
		printf("%d\n",1LL*fc[n-i]*ifac[i]%Q);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:102:38: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
   printf("%d\n",1LL*fc[n-i]*ifac[i]%Q);
                                      ^
./Main.cpp:67:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:89: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