Submission #1193104
Source Code Expand
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
int t=1,sum=0;char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') t=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
sum=sum*10+ch-'0',ch=getchar();
return t*sum;
}
const int Max=6e5,mod=924844033;
int fir[Max],siz[Max],f[Max],g[Max],fac[Max],inv[Max],n,cnt;
int eps[Max],inv_eps[Max],N;
struct edge
{
int to,nxt;
edge () {}
edge (int x,int y)
{
to=y; nxt=fir[x];
fir[x]=cnt;
}
}e[Max<<1];
void add(int x,int y)
{
e[++cnt]=edge(x,y);
e[++cnt]=edge(y,x);
}
int pul(int x,int y)
{
x+=y;
if(x>=mod) x-=mod;
return x;
}
int dec(int x,int y)
{
x-=y;
if(x<0) x+=mod;
return x;
}
void up(int &x,int y)
{
x+=y;
if(x>=mod) x-=mod;
}
void dn(int &x,int y)
{
x-=y;
if(x<0) x+=mod;
}
int fpm(int x,int y)
{
int ans=1;
for(;y;y>>=1,x=1LL*x*x%mod)
if(y&1)
ans=1LL*ans*x%mod;
return ans;
}
void get_ready()
{
int W=fpm(5,(mod-1)/N),IW=fpm(W,mod-2),i;
eps[0]=inv_eps[0]=1;
for(i=1;i<N;i++)
eps[i]=1LL*eps[i-1]*W%mod,
inv_eps[i]=1LL*inv_eps[i-1]*IW%mod;
}
void dft(int *x,int n,int *Eps)
{
int i,j,k,u,t,wn,w;
for(i=j=0;i<n;i++)
{
if(i<j) swap(x[i],x[j]);
for(k=n>>1;(j^=k)<k;k>>=1);
}
for(i=1;i<n;i<<=1)
{
wn=(N/i)>>1;
for(j=0;j<n;j+=i<<1)
for(k=w=0;k<i;k++,w+=wn)
{
u=x[j+k]; t=1LL*Eps[w]*x[j+k+i]%mod;
x[j+k]=pul(u,t);
x[j+k+i]=dec(u,t);
}
}
}
void idft(int *x,int n,int *Eps)
{
dft(x,n,Eps);
int Inv=fpm(n,mod-2),i;
for(i=0;i<n;i++)
x[i]=1LL*x[i]*Inv%mod;
}
void dfs(int x,int p)
{
int i,v; siz[x]=1;
for(i=fir[x];i;i=e[i].nxt)
if(e[i].to!=p)
{
v=e[i].to;
dfs(v,x);
g[siz[v]]++;
siz[x]+=siz[v];
}
g[n-siz[x]]++;
}
int C(int x,int y)
{
if(x<y) return 0;
return 1LL*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
int i,x,y;
n=read();
fac[0]=inv[0]=inv[1]=1;
for(i=2;i<=n;i++)
inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
for(i=1;i<=n;i++)
fac[i]=1LL*fac[i-1]*i%mod,
inv[i]=1LL*inv[i-1]*inv[i]%mod;
for(i=1;i<n;i++)
{
x=read(); y=read();
add(x,y);
}
dfs(1,0);
for(i=0;i<=n;i++)
f[i]=inv[i];
for(i=1;i<=n;i++)
g[i]=1LL*g[i]*fac[i]%mod;
for(i=0;i<n-i;i++)
swap(g[i],g[n-i]);
for(N=1;N<=(n+n);N<<=1);
get_ready();
dft(f,N,eps); dft(g,N,eps);
for(i=0;i<N;i++) f[i]=1LL*f[i]*g[i]%mod;
idft(f,N,inv_eps);
for(i=1;i<=n;i++)
printf("%d\n",dec(1LL*n*C(n,i)%mod,1LL*f[n-i]*inv[i]%mod));
}
Submission Info
Submission Time |
|
Task |
F - Many Easy Problems |
User |
c_2h |
Language |
C++14 (GCC 5.4.1) |
Score |
1900 |
Code Size |
2546 Byte |
Status |
AC |
Exec Time |
156 ms |
Memory |
32512 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 |
148 ms |
24576 KB |
doublestar1 |
AC |
146 ms |
24576 KB |
doublestar2 |
AC |
147 ms |
24576 KB |
doublestar3 |
AC |
146 ms |
24576 KB |
doublestar4 |
AC |
147 ms |
24704 KB |
example0 |
AC |
4 ms |
16512 KB |
example1 |
AC |
4 ms |
16512 KB |
example2 |
AC |
4 ms |
16512 KB |
line0 |
AC |
155 ms |
32512 KB |
line1 |
AC |
155 ms |
32512 KB |
line2 |
AC |
155 ms |
32512 KB |
line3 |
AC |
155 ms |
32512 KB |
line4 |
AC |
154 ms |
32512 KB |
maxrand0 |
AC |
155 ms |
24576 KB |
maxrand1 |
AC |
155 ms |
24576 KB |
maxrand10 |
AC |
156 ms |
24576 KB |
maxrand11 |
AC |
155 ms |
24576 KB |
maxrand12 |
AC |
156 ms |
24576 KB |
maxrand13 |
AC |
155 ms |
24576 KB |
maxrand14 |
AC |
155 ms |
24576 KB |
maxrand15 |
AC |
155 ms |
24576 KB |
maxrand16 |
AC |
154 ms |
24576 KB |
maxrand17 |
AC |
155 ms |
24576 KB |
maxrand18 |
AC |
156 ms |
24576 KB |
maxrand19 |
AC |
154 ms |
24576 KB |
maxrand2 |
AC |
154 ms |
24576 KB |
maxrand3 |
AC |
155 ms |
24576 KB |
maxrand4 |
AC |
155 ms |
24576 KB |
maxrand5 |
AC |
154 ms |
24576 KB |
maxrand6 |
AC |
156 ms |
24576 KB |
maxrand7 |
AC |
155 ms |
24576 KB |
maxrand8 |
AC |
154 ms |
24576 KB |
maxrand9 |
AC |
155 ms |
24576 KB |
rand0 |
AC |
5 ms |
16640 KB |
rand1 |
AC |
4 ms |
16512 KB |
rand2 |
AC |
4 ms |
16640 KB |
rand3 |
AC |
5 ms |
16640 KB |
rand4 |
AC |
4 ms |
16512 KB |
rand5 |
AC |
5 ms |
16640 KB |
rand6 |
AC |
4 ms |
16640 KB |
rand7 |
AC |
5 ms |
16640 KB |
rand8 |
AC |
4 ms |
16512 KB |
rand9 |
AC |
4 ms |
16512 KB |
star0 |
AC |
144 ms |
24576 KB |
star1 |
AC |
143 ms |
24576 KB |
star2 |
AC |
143 ms |
24576 KB |
star3 |
AC |
148 ms |
24576 KB |
star4 |
AC |
145 ms |
24576 KB |