Submission #1161408
Source Code Expand
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define pp pop_back
#define mp make_pair
#define pb push_back
#define rep(x, a, b) for(int x=a; x<=b; x++)
#define drp(x, a, b) for(int x=a; x>=b; x--)
typedef long long ll;
const int mod=924844033;
const int N=200200;
const int G=5;
int ans[N], n, m, l, rev[N<<2], fac[N], inv[N], f[N<<2], u[N], v[N], g[N<<2], head[N], cnt, siz[N], c[N];
ll read(){
ll x=0; char ch=getchar();
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
return x;
}
void write(ll x){
if(x<10)
{
putchar(x+'0');
return;
}
write(x/10);
putchar(x%10+'0');
}
struct Edge{
int to, next;
}edge[N<<1];
void AddEdge(int u, int v){
edge[++cnt]=(Edge){ v, head[u] }, head[u]=cnt;
edge[++cnt]=(Edge){ u, head[v] }, head[v]=cnt;
}
void dfs(int u, int fa){
siz[u]=1;
for(int i=head[u]; i; i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
dfs(v, u);
c[n-siz[v]]--;
siz[u]+=siz[v];
}
c[siz[u]]--;
}
int power(int a, int k){
int ret=1;
while(k)
{
if(k&1) ret=1ll*ret*a%mod;
a=1ll*a*a%mod; k>>=1;
}
return ret;
}
void DFT(int *a, int n, int f){
rep(i, 0, n-1) if(i<rev[i]) swap(a[i], a[rev[i]]);
for(int i=1, t=1; i<n; i<<=1, t++)
{
int wn=power(G, f?(mod-1-((mod-1)>>t)):((mod-1)>>t));
for(int j=0; j<n; j+=i<<1)
{
int w=1;
for(int k=0; k<i; k++, w=1ll*w*wn%mod)
{
int u=a[j+k], v=1ll*w*a[j+k+i]%mod;
a[j+k]=(u+v)%mod; a[j+k+i]=(u+mod-v)%mod;
}
}
}
if(f)
{
int v=power(n, mod-2);
rep(i, 0, n-1) a[i]=1ll*a[i]*v%mod;
}
}
int main(){
n=read();
fac[0]=1;
rep(i, 1, n) fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=power(fac[n], mod-2);
drp(i, n, 1) inv[i-1]=1ll*inv[i]*i%mod;
rep(i, 1, n-1){ u[i]=read(), v[i]=read(); AddEdge(u[i], v[i]); }
rep(i, 1, n-1) c[i]=mod;
dfs(1, 0);
c[n]=n;
rep(i, 1, n) f[i]=1ll*c[i]*fac[i]%mod;
rep(i, 0, n) g[n-i]=inv[i];
for(m=1; m<=((n<<1)|1); m<<=1) l++;
rep(i, 0, m-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
DFT(f, m, 0); DFT(g, m, 0);
rep(i, 0, m-1) f[i]=1ll*f[i]*g[i]%mod;
DFT(f, m, 1);
rep(k, 1, n) ans[k]=1ll*inv[k]*f[n+k]%mod;
rep(i, 1, n) write(ans[i]), puts("");
}
Submission Info
Submission Time |
|
Task |
F - Many Easy Problems |
User |
naive_owo_naive |
Language |
C++14 (GCC 5.4.1) |
Score |
1900 |
Code Size |
2443 Byte |
Status |
AC |
Exec Time |
179 ms |
Memory |
28928 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 |
167 ms |
20864 KB |
doublestar1 |
AC |
167 ms |
20864 KB |
doublestar2 |
AC |
167 ms |
20992 KB |
doublestar3 |
AC |
167 ms |
20864 KB |
doublestar4 |
AC |
168 ms |
20992 KB |
example0 |
AC |
4 ms |
12544 KB |
example1 |
AC |
3 ms |
12544 KB |
example2 |
AC |
3 ms |
12544 KB |
line0 |
AC |
175 ms |
28928 KB |
line1 |
AC |
175 ms |
28800 KB |
line2 |
AC |
175 ms |
28928 KB |
line3 |
AC |
176 ms |
28800 KB |
line4 |
AC |
175 ms |
28800 KB |
maxrand0 |
AC |
177 ms |
20992 KB |
maxrand1 |
AC |
176 ms |
20992 KB |
maxrand10 |
AC |
176 ms |
20992 KB |
maxrand11 |
AC |
175 ms |
20992 KB |
maxrand12 |
AC |
175 ms |
20992 KB |
maxrand13 |
AC |
176 ms |
20992 KB |
maxrand14 |
AC |
176 ms |
20992 KB |
maxrand15 |
AC |
175 ms |
20992 KB |
maxrand16 |
AC |
175 ms |
20992 KB |
maxrand17 |
AC |
176 ms |
20992 KB |
maxrand18 |
AC |
176 ms |
20992 KB |
maxrand19 |
AC |
179 ms |
20992 KB |
maxrand2 |
AC |
175 ms |
20992 KB |
maxrand3 |
AC |
175 ms |
20992 KB |
maxrand4 |
AC |
175 ms |
20992 KB |
maxrand5 |
AC |
175 ms |
20992 KB |
maxrand6 |
AC |
175 ms |
20992 KB |
maxrand7 |
AC |
177 ms |
20992 KB |
maxrand8 |
AC |
175 ms |
20992 KB |
maxrand9 |
AC |
176 ms |
20992 KB |
rand0 |
AC |
6 ms |
12544 KB |
rand1 |
AC |
3 ms |
12544 KB |
rand2 |
AC |
4 ms |
12544 KB |
rand3 |
AC |
5 ms |
12544 KB |
rand4 |
AC |
4 ms |
12544 KB |
rand5 |
AC |
5 ms |
12544 KB |
rand6 |
AC |
4 ms |
12544 KB |
rand7 |
AC |
5 ms |
12544 KB |
rand8 |
AC |
4 ms |
12544 KB |
rand9 |
AC |
4 ms |
12544 KB |
star0 |
AC |
164 ms |
20992 KB |
star1 |
AC |
164 ms |
20992 KB |
star2 |
AC |
164 ms |
20992 KB |
star3 |
AC |
164 ms |
20992 KB |
star4 |
AC |
164 ms |
20992 KB |