Submission #2115312
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)%Mod; 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=2;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)%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
Submission Time |
|
Task |
F - Many Easy Problems |
User |
lzjzlj |
Language |
C++14 (GCC 5.4.1) |
Score |
1900 |
Code Size |
2574 Byte |
Status |
AC |
Exec Time |
251 ms |
Memory |
54656 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1900 / 1900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2 |
All |
doublestar0, doublestar1, doublestar2, doublestar3, doublestar4, example0, example1, example2, line0, line1, line2, line3, line4, maxrand0, maxrand1, maxrand10, maxrand11, maxrand12, maxrand13, maxrand14, maxrand15, maxrand16, maxrand17, maxrand18, maxrand19, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, rand0, rand1, rand2, rand3, rand4, rand5, rand6, rand7, rand8, rand9, star0, star1, star2, star3, star4 |
Case Name |
Status |
Exec Time |
Memory |
doublestar0 |
AC |
237 ms |
45184 KB |
doublestar1 |
AC |
236 ms |
45184 KB |
doublestar2 |
AC |
236 ms |
45184 KB |
doublestar3 |
AC |
236 ms |
45184 KB |
doublestar4 |
AC |
236 ms |
45184 KB |
example0 |
AC |
6 ms |
22784 KB |
example1 |
AC |
6 ms |
22784 KB |
example2 |
AC |
6 ms |
22784 KB |
line0 |
AC |
246 ms |
54656 KB |
line1 |
AC |
246 ms |
54656 KB |
line2 |
AC |
247 ms |
54656 KB |
line3 |
AC |
246 ms |
54656 KB |
line4 |
AC |
246 ms |
54656 KB |
maxrand0 |
AC |
247 ms |
45440 KB |
maxrand1 |
AC |
248 ms |
45440 KB |
maxrand10 |
AC |
247 ms |
45440 KB |
maxrand11 |
AC |
247 ms |
45440 KB |
maxrand12 |
AC |
247 ms |
45440 KB |
maxrand13 |
AC |
247 ms |
45440 KB |
maxrand14 |
AC |
247 ms |
45440 KB |
maxrand15 |
AC |
250 ms |
45440 KB |
maxrand16 |
AC |
251 ms |
45440 KB |
maxrand17 |
AC |
251 ms |
45440 KB |
maxrand18 |
AC |
247 ms |
45440 KB |
maxrand19 |
AC |
249 ms |
45440 KB |
maxrand2 |
AC |
248 ms |
45440 KB |
maxrand3 |
AC |
247 ms |
45440 KB |
maxrand4 |
AC |
249 ms |
45440 KB |
maxrand5 |
AC |
247 ms |
45440 KB |
maxrand6 |
AC |
248 ms |
45440 KB |
maxrand7 |
AC |
247 ms |
45440 KB |
maxrand8 |
AC |
248 ms |
45440 KB |
maxrand9 |
AC |
248 ms |
45440 KB |
rand0 |
AC |
9 ms |
22784 KB |
rand1 |
AC |
6 ms |
22784 KB |
rand2 |
AC |
8 ms |
22784 KB |
rand3 |
AC |
9 ms |
22784 KB |
rand4 |
AC |
7 ms |
22784 KB |
rand5 |
AC |
9 ms |
22784 KB |
rand6 |
AC |
8 ms |
22784 KB |
rand7 |
AC |
9 ms |
22784 KB |
rand8 |
AC |
7 ms |
22784 KB |
rand9 |
AC |
8 ms |
22784 KB |
star0 |
AC |
237 ms |
45184 KB |
star1 |
AC |
233 ms |
45184 KB |
star2 |
AC |
233 ms |
45184 KB |
star3 |
AC |
233 ms |
45184 KB |
star4 |
AC |
233 ms |
45184 KB |