Submission #907163
Source Code Expand
#include<bits/stdc++.h>
#define N (1<<19)
#define Q 924844033
using namespace std;
inline int qp(int a,int p){
int r=1;
while(p){
if(p&1) r=1LL*a*r%Q;
a=1LL*a*a%Q;
p>>=1;
}
return r;
}
inline int inv(int x){
return qp(x,Q-2);
}
int ans[N],cnt[N],sz[N],n,fac[N],ifac[N],fa[N],fb[N],fc[N];
int rt[30],irt[30];
vector<int> g[N];
int build_sz(int u,int p){
sz[u]=1;
int tmp=n-1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==p) continue;
sz[u]+=build_sz(v,u);
cnt[sz[v]]--;
if(cnt[sz[v]]<0) cnt[sz[v]]+=Q;
tmp-=sz[v];
}
cnt[tmp]--;
if(cnt[tmp]<0) cnt[tmp]+=Q;
return sz[u];
}
void FFT(int x[], bool pos){
for (int i=1, j=0; i<N; ++i){
for (int k=N>>1; !((j^=k)&k); k>>=1) ;
if (i>j) swap(x[i], x[j]);
}
for (int k=2; k<=N; k<<=1){
long long om = pos?rt[__lg(k)]:irt[__lg(k)];
for (int j=0; j<N; j+=k){
long long mul = 1;
for (int i=j; i<j+k/2; i++){
int a = x[i], b = 1LL*x[i+k/2]*mul%Q;
x[i] = (a + b)%Q;
x[i+k/2] = (a + Q - b)%Q;
mul = mul*om%Q;
}
}
}
}
void mul(int a[],int b[],int c[]){
FFT(a,true);
FFT(b,true);
for(int i=0;i<N;i++){
c[i]=1LL*a[i]*b[i]%Q;
}
FFT(c,false);
int iN=inv(N);
for(int i=0;i<N;i++){
c[i]=1LL*iN*c[i]%Q;
}
}
int main(){
int a,b;
scanf("%d",&n);
fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++){
fac[i]=1LL*fac[i-1]*i%Q;
ifac[i]=1LL*ifac[i-1]*inv(i)%Q;
}
bool flag=true;
for(int gn=2;flag;gn++){
int tmp=qp(gn,441);
flag=false;
for(int j=0;j<21;j++){
rt[21-j]=tmp;
if(tmp==1){
flag=true;
break;
}
tmp=1LL*tmp*tmp%Q;
}
}
for(int j=1;j<=21;j++) irt[j]=inv(rt[j]);
cnt[n]=n;
for(int i=0;i<n-1;i++){
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
build_sz(1,0);
for(int i=0;i<=n;i++){
fa[n-i]=1LL*cnt[i]*fac[i]%Q;
}
for(int i=0;i<=n;i++){
fb[i]=ifac[i];
}
mul(fa,fb,fc);
for(int i=1;i<=n;i++){
printf("%d\n",1LL*fc[n-i]*ifac[i]%Q);
}
return 0;
}
Submission Info
Submission Time
2016-10-01 22:48:30+0900
Task
F - Many Easy Problems
User
aaaaajack
Language
C++14 (GCC 5.4.1)
Score
1900
Code Size
2137 Byte
Status
AC
Exec Time
302 ms
Memory
43264 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:102:38: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
printf("%d\n",1LL*fc[n-i]*ifac[i]%Q);
^
./Main.cpp:67:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:89:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
^
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
242 ms
29560 KB
doublestar1
AC
242 ms
29560 KB
doublestar2
AC
242 ms
29560 KB
doublestar3
AC
241 ms
29560 KB
doublestar4
AC
242 ms
29560 KB
example0
AC
135 ms
18688 KB
example1
AC
135 ms
18688 KB
example2
AC
136 ms
18688 KB
line0
AC
266 ms
43136 KB
line1
AC
266 ms
43136 KB
line2
AC
267 ms
43264 KB
line3
AC
266 ms
43136 KB
line4
AC
267 ms
43136 KB
maxrand0
AC
271 ms
29568 KB
maxrand1
AC
269 ms
29568 KB
maxrand10
AC
270 ms
29568 KB
maxrand11
AC
270 ms
29568 KB
maxrand12
AC
270 ms
29568 KB
maxrand13
AC
270 ms
29568 KB
maxrand14
AC
270 ms
29568 KB
maxrand15
AC
270 ms
29568 KB
maxrand16
AC
270 ms
29568 KB
maxrand17
AC
271 ms
29568 KB
maxrand18
AC
270 ms
29568 KB
maxrand19
AC
270 ms
29568 KB
maxrand2
AC
271 ms
29568 KB
maxrand3
AC
270 ms
29568 KB
maxrand4
AC
270 ms
29568 KB
maxrand5
AC
270 ms
29568 KB
maxrand6
AC
302 ms
29568 KB
maxrand7
AC
276 ms
29568 KB
maxrand8
AC
274 ms
29568 KB
maxrand9
AC
283 ms
29696 KB
rand0
AC
137 ms
18816 KB
rand1
AC
134 ms
18688 KB
rand2
AC
136 ms
18816 KB
rand3
AC
136 ms
18816 KB
rand4
AC
135 ms
18688 KB
rand5
AC
136 ms
18816 KB
rand6
AC
136 ms
18816 KB
rand7
AC
136 ms
18816 KB
rand8
AC
135 ms
18688 KB
rand9
AC
135 ms
18688 KB
star0
AC
235 ms
29940 KB
star1
AC
235 ms
29940 KB
star2
AC
236 ms
29940 KB
star3
AC
236 ms
29940 KB
star4
AC
236 ms
29940 KB