Submission #1836830
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1<<18,mod=924844033;
int n,size[maxn];
ll fac[maxn],finv[maxn],a[maxn<<1],b[maxn<<1],c[maxn<<1];
vector<int> g[maxn];
inline ll qpow(ll a,ll n){
ll res=1;
while(n){
if(n&1)
res=res*a%mod;
a=a*a%mod;
n>>=1;
}
return res;
}
void dfs(int pos,int fa){
size[pos]=1;
for(int i=0,v;i<g[pos].size();++i)
if((v=g[pos][i])!=fa){
dfs(v,pos);
size[pos]+=size[v];
++a[size[v]];
++a[n-size[v]];
}
}
inline int rev(int id,int len){
int res=0;
for(int i=1;i<len;i<<=1){
res<<=1;
if(id&i)
res|=1;
}
return res;
}
inline void fft(ll*a,int len,int dft){
for(int i=0;i<len;++i)
if(i<rev(i,len))
swap(a[i],a[rev(i,len)]);
for(int i=2;i<=len;i<<=1){
ll w=qpow(5,(mod-1)/i);
if(dft==-1)
w=qpow(w,mod-2);
for(int j=0;j<len;j+=i){
ll ww=1;
for(int k=0;k<(i>>1);++k,ww=ww*w%mod){
ll x=a[j+k],y=a[j+k+(i>>1)]*ww%mod;
a[j+k]=(x+y)%mod;
a[j+k+(i>>1)]=(x-y+mod)%mod;
}
}
}
if(dft==-1){
int inv=qpow(len,mod-2);
for(int i=0;i<len;++i)
a[i]=a[i]*inv%mod;
}
}
int main(){
fac[0]=1;
for(int i=1;i<maxn;++i)
fac[i]=fac[i-1]*i%mod;
finv[maxn-1]=qpow(fac[maxn-1],mod-2);
for(int i=maxn-1;i;--i)
finv[i-1]=finv[i]*i%mod;
scanf("%d",&n);
for(int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<n;++i)
a[i]=a[i]*fac[i]%mod;
for(int i=0;i<=n;++i)
b[i]=finv[n-i];
fft(a,maxn<<1,1);
fft(b,maxn<<1,1);
for(int i=0;i<(maxn<<1);++i)
c[i]=a[i]*b[i]%mod;
fft(c,maxn<<1,-1);
for(int i=1;i<=n;++i)
printf("%lld\n",(n*fac[n]%mod*finv[i]%mod*finv[n-i]%mod-finv[i]*c[n+i]%mod+mod)%mod);
return 0;
}
Submission Info
Submission Time
2017-12-06 18:20:52+0900
Task
F - Many Easy Problems
User
guo
Language
C++14 (GCC 5.4.1)
Score
1900
Code Size
1798 Byte
Status
AC
Exec Time
282 ms
Memory
44928 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:70:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:72:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&u,&v);
^
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
247 ms
32120 KB
doublestar1
AC
246 ms
32120 KB
doublestar2
AC
247 ms
32120 KB
doublestar3
AC
249 ms
32120 KB
doublestar4
AC
248 ms
32120 KB
example0
AC
174 ms
22784 KB
example1
AC
174 ms
22784 KB
example2
AC
175 ms
22784 KB
line0
AC
268 ms
44928 KB
line1
AC
263 ms
44928 KB
line2
AC
264 ms
44928 KB
line3
AC
263 ms
44928 KB
line4
AC
264 ms
44928 KB
maxrand0
AC
274 ms
32000 KB
maxrand1
AC
275 ms
32000 KB
maxrand10
AC
274 ms
32000 KB
maxrand11
AC
275 ms
32000 KB
maxrand12
AC
274 ms
32000 KB
maxrand13
AC
276 ms
32000 KB
maxrand14
AC
274 ms
32000 KB
maxrand15
AC
275 ms
32000 KB
maxrand16
AC
274 ms
32000 KB
maxrand17
AC
275 ms
32000 KB
maxrand18
AC
282 ms
32000 KB
maxrand19
AC
277 ms
32000 KB
maxrand2
AC
275 ms
32000 KB
maxrand3
AC
278 ms
32000 KB
maxrand4
AC
277 ms
32000 KB
maxrand5
AC
281 ms
32000 KB
maxrand6
AC
276 ms
32000 KB
maxrand7
AC
279 ms
32000 KB
maxrand8
AC
279 ms
32000 KB
maxrand9
AC
274 ms
32000 KB
rand0
AC
176 ms
22912 KB
rand1
AC
175 ms
22784 KB
rand2
AC
175 ms
22912 KB
rand3
AC
175 ms
22912 KB
rand4
AC
174 ms
22784 KB
rand5
AC
175 ms
22912 KB
rand6
AC
176 ms
22912 KB
rand7
AC
175 ms
22912 KB
rand8
AC
174 ms
22784 KB
rand9
AC
175 ms
22784 KB
star0
AC
241 ms
32500 KB
star1
AC
242 ms
32500 KB
star2
AC
243 ms
32500 KB
star3
AC
241 ms
32500 KB
star4
AC
241 ms
32500 KB