Submission #2115231

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL Mod = 924844033; // 2^21 * 3^2 * 7^2 g=5;
const LL N = 800010;
struct node{LL x,y,next;}edge[N]; LL len,first[N];
void ins(LL x,LL y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;}

LL qpow(LL x,LL k,LL mo){LL s=1; while(k){if(k&1) s=(s*x)%mo; x=(x*x)%mo; k>>=1;} return s;}
/*
void check()
{

  LL x=Mod-1;
  for(LL i=2;i*i<=x;i++)
  {
    LL p=0;
    while(x%i==0) p++,x/=i;
    if(p) prLLf("%d^%d\n",i,p);
  }
  for(LL i=2;i;i++)
  {
    LL x=Mod-1; bool bk=true;
    for(LL j=2;j*j<=x;j++)
    {
      if(x%j==0)
      {
        if(qpow(i,j,Mod) == 1) bk=false;
        if(qpow(i,x/j,Mod) == 1) bk=false;
      }
    }
    if(bk){prLLf("%LLd\n",i); break;}
  }
}*/

inline LL read()
{
  char ch=getchar(); LL p=0; LL f=1;
  while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+(ch-'0'); ch=getchar();}
  return p*f;
}

LL siz[N];
void dfs(LL x,LL f)
{
  siz[x]=1;
  for(LL k=first[x];k!=-1;k=edge[k].next)
  {
    LL y=edge[k].y;
    if(y==f) continue;
    dfs(y,x); siz[x]+=siz[y];
  }
}

LL jc[N]; LL R[N];

void NFT(LL *a,LL n,LL fh)
{
  for(LL i=1;i<n;i++) if(R[i] > i) swap(a[R[i]],a[i]);
  for(LL i=1;i<n;i<<=1)
  {
    LL gn = qpow(5LL , (Mod-1) / (i<<1) ,Mod);
    for(LL j=0;j<n;j+=(i<<1))
    {
      LL g=1;
      for(LL k=0;k<i;k++,g=(g*gn)%Mod)
      {
        LL x=a[j+k]; LL y=a[j+k+i]*g%Mod;
        a[j+k] = x+y; a[j+k+i] = (x-y+Mod)%Mod;
      }
    }
  }
  if(fh==-1) reverse(a+1,a+n);
}

void NTT(LL *a,LL *b,LL n,LL m)
{
  m+=n; LL l=0; for(n=1;n<=m;n<<=1) l++;
  for(LL i=1;i<n;i++) R[i] = (R[i>>1]>>1) | ((i&1) << (l-1));

  NFT(a,n,1); NFT(b,n,1);
  for(LL i=0;i<n;i++) a[i] = (a[i]*b[i])%Mod;
  NFT(a,n,-1); LL ny = qpow(n,Mod-2,Mod);
  for(LL i=0;i<n;i++) a[i] = (a[i]*ny)%Mod;
}

LL a[N],b[N],c[N],n;

int main()
{

  //check();
  n=read(); len=0; memset(first,-1,sizeof(first));
  for(LL i=1;i<n;i++){LL x=read(),y=read(); ins(x,y); ins(y,x);}
  memset(siz,0,sizeof(siz)); dfs(1,0);

  jc[0]=1; for(LL i=1;i<=n;i++) jc[i] = (jc[i-1] * i)%Mod;
  
  for(LL i=0;i<=n;i++) a[i]=jc[i];
  for(LL i=0;i<=n;i++) c[n]++,c[siz[i]]--,c[n-siz[i]]--; c[n]++;
  for(LL i=0;i<=n;i++) a[i]=(a[i]*c[i]+Mod)%Mod,b[i]=qpow(jc[n-i],Mod-2,Mod);
  
  //a[1]=1; a[2]=2;
  //b[1]=1; b[2]=3;
  NTT(a,b,n,n);

  for(LL i=1;i<=n;i++) printf("%lld\n",a[n+i] * qpow(jc[i],Mod-2,Mod) % Mod);

  return 0;
}

Submission Info

Judge Result