Submission #1810763
Source Code Expand
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<ctime> #include<utility> #include<list> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; const ll p=924844033; const ll g=5; ll fp(ll a,ll b) { ll s=1; while(b) { if(b&1) s=s*a%p; a=a*a%p; b>>=1; } return s; } namespace ntt { ll w1[1000010]; ll w2[1000010]; int rev[1000010]; int n; void init() { #ifdef DEBUG n=16; #else n=524288; #endif int i; for(i=1;i<=n;i<<=1) { w1[i]=fp(g,(p-1)/i); w2[i]=fp(w1[i],p-2); } rev[0]=0; for(i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|(i&1?n>>1:0); } void ntt(ll *a,int t) { int i,j,k; ll u,v,w,wn; for(i=0;i<n;i++) if(rev[i]<i) swap(a[i],a[rev[i]]); for(i=2;i<=n;i<<=1) { wn=(t==1?w1[i]:w2[i]); for(j=0;j<n;j+=i) { w=1; for(k=j;k<j+i/2;k++) { u=a[k]; v=a[k+i/2]*w%p; a[k]=(u+v)%p; a[k+i/2]=(u-v)%p; w=w*wn%p; } } } if(t==-1) { ll inv=fp(n,p-2); for(i=0;i<n;i++) a[i]=a[i]*inv%p; } } }; ll b[1000010]; ll c[1000010]; ll a[1000010]; ll inv[1000010]; ll fac[1000010]; ll ifac[1000010]; int s[1000010]; int n; list<int> l[200010]; ll num[1000010]; void dfs(int x,int fa) { s[x]=1; for(auto v:l[x]) if(v!=fa) { dfs(v,x); s[x]+=s[v]; num[s[v]]--; num[n-s[v]]--; } } int main() { #ifdef DEBUG freopen("b.in","r",stdin); freopen("b.out","w",stdout); #endif scanf("%d",&n); int i,x,y; for(i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); l[x].push_back(y); l[y].push_back(x); } inv[0]=inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1; for(i=2;i<=n;i++) { inv[i]=-(p/i)*inv[p%i]%p; fac[i]=fac[i-1]*i%p; ifac[i]=ifac[i-1]*inv[i]%p; } dfs(1,0); num[n]=n; for(i=0;i<=n;i++) b[i]=num[n-i]*fac[n-i]%p; for(i=0;i<=n;i++) c[i]=ifac[i]; ntt::init(); ntt::ntt(b,1); ntt::ntt(c,1); for(i=0;i<ntt::n;i++) a[i]=b[i]*c[i]%p; ntt::ntt(a,-1); for(i=1;i<=n;i++) { ll ans=a[n-i]*ifac[i]%p; ans=(ans+p)%p; printf("%lld\n",ans); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Many Easy Problems |
User | yww |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 2201 Byte |
Status | AC |
Exec Time | 293 ms |
Memory | 78080 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:108:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:112:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&x,&y); ^
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 | 217 ms | 65792 KB |
doublestar1 | AC | 217 ms | 65792 KB |
doublestar2 | AC | 217 ms | 65792 KB |
doublestar3 | AC | 217 ms | 65792 KB |
doublestar4 | AC | 218 ms | 65792 KB |
example0 | AC | 134 ms | 47360 KB |
example1 | AC | 134 ms | 47360 KB |
example2 | AC | 134 ms | 47360 KB |
line0 | AC | 230 ms | 77952 KB |
line1 | AC | 230 ms | 77952 KB |
line2 | AC | 230 ms | 78080 KB |
line3 | AC | 230 ms | 77952 KB |
line4 | AC | 230 ms | 77952 KB |
maxrand0 | AC | 246 ms | 66176 KB |
maxrand1 | AC | 248 ms | 66176 KB |
maxrand10 | AC | 247 ms | 66176 KB |
maxrand11 | AC | 247 ms | 66048 KB |
maxrand12 | AC | 247 ms | 66176 KB |
maxrand13 | AC | 247 ms | 66176 KB |
maxrand14 | AC | 250 ms | 66176 KB |
maxrand15 | AC | 248 ms | 66176 KB |
maxrand16 | AC | 247 ms | 66176 KB |
maxrand17 | AC | 250 ms | 66176 KB |
maxrand18 | AC | 255 ms | 66176 KB |
maxrand19 | AC | 247 ms | 66176 KB |
maxrand2 | AC | 251 ms | 66176 KB |
maxrand3 | AC | 249 ms | 66176 KB |
maxrand4 | AC | 253 ms | 66176 KB |
maxrand5 | AC | 249 ms | 66176 KB |
maxrand6 | AC | 255 ms | 66176 KB |
maxrand7 | AC | 250 ms | 66176 KB |
maxrand8 | AC | 253 ms | 66176 KB |
maxrand9 | AC | 249 ms | 66176 KB |
rand0 | AC | 135 ms | 47616 KB |
rand1 | AC | 134 ms | 47360 KB |
rand2 | AC | 135 ms | 47488 KB |
rand3 | AC | 135 ms | 47488 KB |
rand4 | AC | 134 ms | 47360 KB |
rand5 | AC | 135 ms | 47488 KB |
rand6 | AC | 135 ms | 47488 KB |
rand7 | AC | 135 ms | 47616 KB |
rand8 | AC | 134 ms | 47360 KB |
rand9 | AC | 134 ms | 47488 KB |
star0 | AC | 215 ms | 65792 KB |
star1 | AC | 214 ms | 65792 KB |
star2 | AC | 215 ms | 65792 KB |
star3 | AC | 293 ms | 65792 KB |
star4 | AC | 215 ms | 65792 KB |