Submission #910261
Source Code Expand
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int,int>pi;
const int mod=924844033,g=5,Maxn=200020;
int powmod(int x,int y,int mod){
int ret=1;
while(y){
if(y&1)ret=1LL*ret*x%mod;
y>>=1;
x=1LL*x*x%mod;
}
return ret;
}
vector<int>G[Maxn];
int n;
int fac[Maxn],rev[Maxn];
int sz[Maxn];
int ans[Maxn];
int gp[100],rgp[100];
int a[1<<20],b[1<<20];
int C(int x,int y){
if(x<y||y<0)return 0;
return 1LL*fac[x]*rev[y]%mod*rev[x-y]%mod;
}
void precal(){
for(int cur=1,tmp=mod-1;~tmp&1;cur++){
tmp>>=1;
gp[cur]=powmod(g,tmp,mod);
rgp[cur]=powmod(gp[cur],mod-2,mod);
}
}
int getrev(int x){
return powmod(x,mod-2,mod);
}
void fft(int *a,int n,int ty=0){
for(int i=0,j=1,k;j<n-1;j++){
for(k=n>>1;i&k;k>>=1)i^=k;i^=k;
if(i<j)swap(a[i],a[j]);
}
for(int k=2,cur=1;k<=n;k<<=1,cur++){
int wn=ty?rgp[cur]:gp[cur];
for(int i=0;i+k<=n;i+=k){
for(int j=0,w=1;j<k>>1;j++,w=1ll*w*wn%mod){
int u=a[i+j],v=1ll*a[i+j+(k>>1)]*w%mod;
a[i+j]=(u+v)%mod;
a[i+j+(k>>1)]=(u-v+mod)%mod;
}
}
}
if(ty){
int rn=getrev(n);
for(int i=0;i<n;i++)a[i]=1ll*a[i]*rn%mod;
}
}
void mul(int *a,int *b,int n){
fft(a,n);
fft(b,n);
for(int i=0;i<n;i++)a[i]=1ll*a[i]*b[i]%mod;
fft(a,n,1);
}
void dfs(int u,int p){
sz[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];if(v==p)continue;
dfs(v,u);
sz[u]+=sz[v];
}
}
int main(){
precal();
fac[0]=fac[1]=rev[0]=rev[1]=1;
for(int i=2;i<Maxn;i++)fac[i]=1LL*fac[i-1]*i%mod;
for(int i=2;i<Maxn;i++)rev[i]=1LL*(mod-mod/i)*rev[mod%i]%mod;
for(int i=2;i<Maxn;i++)rev[i]=1LL*rev[i-1]*rev[i]%mod;
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
int N=1;
while(N<=n)N<<=1;
N<<=1;
for(int i=1;i<=n;i++)a[sz[i]]++,a[n-sz[i]]++;
for(int i=1;i<=n;i++)a[i]=1LL*a[i]*fac[i]%mod;
for(int i=0;i<=n;i++){
b[n-i]=rev[i];
}
mul(a,b,N);
for(int i=n;i<=n+n;i++)ans[i-n]=(1LL*n*C(n,i-n)%mod-1LL*rev[i-n]*a[i]%mod+mod)%mod;
for(int i=1;i<=n;i++)ans[i]=(ans[i]+C(sz[1],i))%mod;
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
return 0;
}
Submission Info
Submission Time
2016-10-02 22:32:48+0900
Task
F - Many Easy Problems
User
ffight
Language
C++14 (GCC 5.4.1)
Score
1900
Code Size
2554 Byte
Status
AC
Exec Time
247 ms
Memory
33536 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:89:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:91:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int u,v;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
220 ms
20728 KB
doublestar1
AC
220 ms
20728 KB
doublestar2
AC
219 ms
20728 KB
doublestar3
AC
219 ms
20728 KB
doublestar4
AC
218 ms
20728 KB
example0
AC
13 ms
6528 KB
example1
AC
13 ms
6528 KB
example2
AC
13 ms
6528 KB
line0
AC
243 ms
33536 KB
line1
AC
243 ms
33536 KB
line2
AC
243 ms
33536 KB
line3
AC
243 ms
33536 KB
line4
AC
243 ms
33536 KB
maxrand0
AC
245 ms
20608 KB
maxrand1
AC
244 ms
20608 KB
maxrand10
AC
244 ms
20608 KB
maxrand11
AC
244 ms
20608 KB
maxrand12
AC
244 ms
20608 KB
maxrand13
AC
246 ms
20608 KB
maxrand14
AC
247 ms
20608 KB
maxrand15
AC
243 ms
20608 KB
maxrand16
AC
247 ms
20608 KB
maxrand17
AC
245 ms
20608 KB
maxrand18
AC
247 ms
20608 KB
maxrand19
AC
245 ms
20608 KB
maxrand2
AC
243 ms
20608 KB
maxrand3
AC
243 ms
20608 KB
maxrand4
AC
243 ms
20608 KB
maxrand5
AC
244 ms
20608 KB
maxrand6
AC
243 ms
20608 KB
maxrand7
AC
243 ms
20608 KB
maxrand8
AC
242 ms
20608 KB
maxrand9
AC
247 ms
20736 KB
rand0
AC
15 ms
6656 KB
rand1
AC
13 ms
6528 KB
rand2
AC
14 ms
6656 KB
rand3
AC
15 ms
6656 KB
rand4
AC
13 ms
6528 KB
rand5
AC
15 ms
6656 KB
rand6
AC
14 ms
6656 KB
rand7
AC
15 ms
6656 KB
rand8
AC
13 ms
6528 KB
rand9
AC
14 ms
6656 KB
star0
AC
213 ms
21236 KB
star1
AC
212 ms
21108 KB
star2
AC
213 ms
21108 KB
star3
AC
212 ms
21108 KB
star4
AC
212 ms
21108 KB