Submission #910306
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------
ll mo=924844033;
int N;
vector<int> E[202020];
int C[202020];
int A[202020];
ll fact[202020];
ll combi(ll N_, ll C_) {
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
if (fact[0]==0) {
inv[1]=fact[0]=factr[0]=1;
for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
}
if(C_<0 || C_>N_) return 0;
return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
void dfs(int cur,int pre) {
C[cur]=1;
FORR(r,E[cur]) if(r!=pre) dfs(r,cur),C[cur]+=C[r];
}
ll modpow(ll a, ll n = mo-2) {
ll r=1;
while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
return r;
}
vector<ll> fft(vector<ll> v, bool rev=false) {
int n=v.size(),i,j,m;
for(i=0,j=1;j<n-1;j++) {
for(int k=n>>1;k>(i^=k);k>>=1);
if(i>j) swap(v[i],v[j]);
}
for(int m=2; m<=n; m*=2) {
ll wn=modpow(5,(mo-1)/m);
if(rev) wn=modpow(wn);
for(i=0;i<n;i+=m) {
ll w=1;
for(int j1=i,j2=i+m/2;j2<i+m;j1++,j2++) {
ll t1=v[j1],t2=w*v[j2]%mo;
v[j1]=t1+t2;
v[j2]=t1+mo-t2;
while(v[j1]>=mo) v[j1]-=mo;
while(v[j2]>=mo) v[j2]-=mo;
w=w*wn%mo;
}
}
}
if(rev) {
ll rv = modpow(n);
FOR(i,n) v[i]=v[i]*rv%mo;
}
return v;
}
vector<ll> MultPoly(vector<ll> P,vector<ll> Q,bool resize=false) {
if(resize) {
int maxind=0,pi=0,qi=0,i;
int s=2;
FOR(i,P.size()) if(norm(P[i])) pi=i;
FOR(i,Q.size()) if(norm(Q[i])) qi=i;
maxind=pi+qi+1;
while(s*2<maxind) s*=2;
P.resize(s*2);Q.resize(s*2);
}
P=fft(P), Q=fft(Q);
for(int i=0;i<P.size();i++) P[i]=P[i]*Q[i]%mo;
return fft(P,true);
}
void solve() {
int i,j,k,l,r,x,y; string s;
cin>>N;
FOR(i,N-1) {
cin>>x>>y;
E[x-1].push_back(y-1);
E[y-1].push_back(x-1);
}
dfs(0,-1);
FOR(x,N) if(C[x]!=N) A[C[x]]++,A[N-C[x]]++;
vector<ll> P(1<<19),Q(1<<19);
fact[0]=1;
FOR(i,N+1) fact[i+1]=fact[i]*(i+1)%mo;
for(i=0;i<=N;i++) {
P[i] = A[i]*fact[i];
Q[N-i] = modpow(fact[i]);
}
vector<ll> R=MultPoly(P,Q);
for(i=1;i<=N;i++) {
ll ret=N*combi(N,i)%mo;
ret -= R[N+i-0]*modpow(fact[i])%mo;
cout<<(ret%mo+mo)%mo<<endl;
}
}
int main(int argc,char** argv){
string s;int i;
if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
FOR(i,argc-1) s+=argv[i+1],s+='\n';
FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
solve(); return 0;
}
Submission Info
Submission Time |
|
Task |
F - Many Easy Problems |
User |
kmjp |
Language |
C++14 (GCC 5.4.1) |
Score |
1900 |
Code Size |
2892 Byte |
Status |
AC |
Exec Time |
1844 ms |
Memory |
50036 KB |
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 |
1742 ms |
41708 KB |
doublestar1 |
AC |
1748 ms |
41580 KB |
doublestar2 |
AC |
1753 ms |
41708 KB |
doublestar3 |
AC |
1752 ms |
41580 KB |
doublestar4 |
AC |
1749 ms |
41708 KB |
example0 |
AC |
455 ms |
30708 KB |
example1 |
AC |
453 ms |
30708 KB |
example2 |
AC |
468 ms |
30708 KB |
line0 |
AC |
1826 ms |
49908 KB |
line1 |
AC |
1828 ms |
50036 KB |
line2 |
AC |
1835 ms |
50036 KB |
line3 |
AC |
1817 ms |
49908 KB |
line4 |
AC |
1819 ms |
49908 KB |
maxrand0 |
AC |
1805 ms |
41716 KB |
maxrand1 |
AC |
1829 ms |
41716 KB |
maxrand10 |
AC |
1816 ms |
41716 KB |
maxrand11 |
AC |
1821 ms |
41716 KB |
maxrand12 |
AC |
1814 ms |
41716 KB |
maxrand13 |
AC |
1815 ms |
41716 KB |
maxrand14 |
AC |
1844 ms |
41716 KB |
maxrand15 |
AC |
1837 ms |
41716 KB |
maxrand16 |
AC |
1822 ms |
41716 KB |
maxrand17 |
AC |
1818 ms |
41716 KB |
maxrand18 |
AC |
1814 ms |
41716 KB |
maxrand19 |
AC |
1796 ms |
41716 KB |
maxrand2 |
AC |
1819 ms |
41716 KB |
maxrand3 |
AC |
1802 ms |
41716 KB |
maxrand4 |
AC |
1831 ms |
41716 KB |
maxrand5 |
AC |
1807 ms |
41716 KB |
maxrand6 |
AC |
1812 ms |
41716 KB |
maxrand7 |
AC |
1810 ms |
41716 KB |
maxrand8 |
AC |
1818 ms |
41716 KB |
maxrand9 |
AC |
1819 ms |
41716 KB |
rand0 |
AC |
575 ms |
30964 KB |
rand1 |
AC |
510 ms |
30708 KB |
rand2 |
AC |
566 ms |
30836 KB |
rand3 |
AC |
574 ms |
30964 KB |
rand4 |
AC |
544 ms |
30836 KB |
rand5 |
AC |
575 ms |
30964 KB |
rand6 |
AC |
564 ms |
30836 KB |
rand7 |
AC |
574 ms |
30964 KB |
rand8 |
AC |
533 ms |
30836 KB |
rand9 |
AC |
552 ms |
30836 KB |
star0 |
AC |
1732 ms |
42088 KB |
star1 |
AC |
1737 ms |
42088 KB |
star2 |
AC |
1739 ms |
42088 KB |
star3 |
AC |
1738 ms |
42088 KB |
star4 |
AC |
1734 ms |
42088 KB |