Submission #1836667
Source Code Expand
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0' || '9'<ch)ch=getchar();
while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
return x;
}
typedef long long ll;
const int N=400009;
const ll md=924844033;
int n,m,l;
int to[N<<1],nxt[N<<1],beg[N],tot;
int rev[N<<1],siz[N];
ll a[N<<1],b[N<<1],fac[N],inv[N];
inline void chk(ll &a){if(a<0)a+=md;}
inline ll qpow(ll a,ll b)
{
ll ret=1ll;
while(b)
{
if(b&1ll)
ret=ret*a%md;
a=a*a%md;
b>>=1;
}
return ret;
}
inline void add(int u,int v)
{
to[++tot]=v;
nxt[tot]=beg[u];
beg[u]=tot;
}
inline void dfs(int u,int fa)
{
a[n]++;siz[u]=1;
for(int i=beg[u];i;i=nxt[i])
if(to[i]!=fa)
{
dfs(to[i],u);
siz[u]+=siz[to[i]];
chk(--a[siz[to[i]]]);
}
chk(--a[n-siz[u]]);
}
inline void NTT(ll *a,int n,bool f)
{
for(int i=0;i<n;i++)
if(i<rev[i])
swap(a[i],a[rev[i]]);
for(int h=2;h<=n;h<<=1)
{
ll w=qpow(5,(md-1)/h);
if(f)w=qpow(w,md-2);
for(int j=0;j<n;j+=h)
{
ll wn=1;
for(int k=j;k<j+(h>>1);k++)
{
ll x=a[k],y=wn*a[k+(h>>1)]%md;
a[k]=(x+y)%md;
a[k+(h>>1)]=(x-y+md)%md;
wn=wn*w%md;
}
}
}
if(f)
for(ll i=0,invn=qpow(n,md-2);i<n;i++)
a[i]=a[i]*invn%md;
}
inline void init()
{
fac[0]=1;
for(ll i=1;i<N;i++)
fac[i]=fac[i-1]*i%md;
inv[N-1]=qpow(fac[N-1],md-2);
for(ll i=N-1;i>=1;i--)
inv[i-1]=inv[i]*i%md;
}
int main()
{
if(fopen("vj.in","r"))
{
freopen("vj.in","r",stdin);
freopen("vj.out","w",stdout);
}
init();
n=read();
for(int i=1,u,v;i<n;i++)
{
u=read();v=read();
add(u,v);add(v,u);
}
dfs(1,1);
for(int i=1;i<=n;i++)
a[i]=a[i]*fac[i]%md;
for(int i=1;i<=n;i++)
b[i]=inv[n-i];
for(m=1,l=0;m<=(n<<1);m<<=1)l++;
for(int i=0;i<m;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
NTT(a,m,0);NTT(b,m,0);
for(int i=0;i<m;i++)
a[i]=a[i]*b[i]%md;
NTT(a,m,1);
for(int i=1;i<=n;i++)
printf("%lld\n",a[n+i]*inv[i]%md);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Many Easy Problems |
User |
xzkkjm_ |
Language |
C++14 (GCC 5.4.1) |
Score |
1900 |
Code Size |
2150 Byte |
Status |
AC |
Exec Time |
185 ms |
Memory |
36736 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:102:29: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("vj.in","r",stdin);
^
./Main.cpp:103:31: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("vj.out","w",stdout);
^
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 |
171 ms |
32896 KB |
doublestar1 |
AC |
171 ms |
32896 KB |
doublestar2 |
AC |
171 ms |
32896 KB |
doublestar3 |
AC |
171 ms |
32896 KB |
doublestar4 |
AC |
171 ms |
32896 KB |
example0 |
AC |
9 ms |
18688 KB |
example1 |
AC |
9 ms |
18688 KB |
example2 |
AC |
9 ms |
18688 KB |
line0 |
AC |
177 ms |
36736 KB |
line1 |
AC |
177 ms |
36736 KB |
line2 |
AC |
177 ms |
36736 KB |
line3 |
AC |
177 ms |
36736 KB |
line4 |
AC |
177 ms |
36736 KB |
maxrand0 |
AC |
180 ms |
32896 KB |
maxrand1 |
AC |
180 ms |
32896 KB |
maxrand10 |
AC |
180 ms |
32896 KB |
maxrand11 |
AC |
180 ms |
32896 KB |
maxrand12 |
AC |
180 ms |
32896 KB |
maxrand13 |
AC |
180 ms |
32896 KB |
maxrand14 |
AC |
181 ms |
32896 KB |
maxrand15 |
AC |
180 ms |
32896 KB |
maxrand16 |
AC |
180 ms |
32896 KB |
maxrand17 |
AC |
180 ms |
32896 KB |
maxrand18 |
AC |
180 ms |
32896 KB |
maxrand19 |
AC |
180 ms |
32896 KB |
maxrand2 |
AC |
180 ms |
32896 KB |
maxrand3 |
AC |
180 ms |
32896 KB |
maxrand4 |
AC |
182 ms |
32896 KB |
maxrand5 |
AC |
180 ms |
32896 KB |
maxrand6 |
AC |
181 ms |
32896 KB |
maxrand7 |
AC |
180 ms |
32896 KB |
maxrand8 |
AC |
180 ms |
32896 KB |
maxrand9 |
AC |
180 ms |
32896 KB |
rand0 |
AC |
11 ms |
18688 KB |
rand1 |
AC |
9 ms |
18688 KB |
rand2 |
AC |
10 ms |
18688 KB |
rand3 |
AC |
11 ms |
18688 KB |
rand4 |
AC |
9 ms |
18688 KB |
rand5 |
AC |
10 ms |
18688 KB |
rand6 |
AC |
10 ms |
18688 KB |
rand7 |
AC |
11 ms |
18688 KB |
rand8 |
AC |
9 ms |
18688 KB |
rand9 |
AC |
9 ms |
18688 KB |
star0 |
AC |
168 ms |
32896 KB |
star1 |
AC |
168 ms |
32896 KB |
star2 |
AC |
168 ms |
32896 KB |
star3 |
AC |
185 ms |
33024 KB |
star4 |
AC |
174 ms |
32896 KB |