Submission #2115310
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL Mod = 924844033; // 2^21 * 3^2 * 7^2 g=5;
const LL N = 800010;
struct node{LL x,y,next;}edge[N]; LL len,first[N];
void ins(LL x,LL y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;}
LL qpow(LL x,LL k,LL mo){LL s=1; while(k){if(k&1) s=(s*x)%mo; x=(x*x)%mo; k>>=1;} return s;}
/*
void check()
{
LL x=Mod-1;
for(LL i=2;i*i<=x;i++)
{
LL p=0;
while(x%i==0) p++,x/=i;
if(p) prLLf("%d^%d\n",i,p);
}
for(LL i=2;i;i++)
{
LL x=Mod-1; bool bk=true;
for(LL j=2;j*j<=x;j++)
{
if(x%j==0)
{
if(qpow(i,j,Mod) == 1) bk=false;
if(qpow(i,x/j,Mod) == 1) bk=false;
}
}
if(bk){prLLf("%LLd\n",i); break;}
}
}*/
inline LL read()
{
char ch=getchar(); LL p=0; LL f=1;
while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0' && ch<='9'){p=p*10+(ch-'0'); ch=getchar();}
return p*f;
}
LL siz[N];
void dfs(LL x,LL f)
{
siz[x]=1;
for(LL k=first[x];k!=-1;k=edge[k].next)
{
LL y=edge[k].y;
if(y==f) continue;
dfs(y,x); siz[x]+=siz[y];
}
}
LL jc[N]; LL R[N];
void NFT(LL *a,LL n,LL fh)
{
for(LL i=1;i<n;i++) if(R[i] > i) swap(a[R[i]],a[i]);
for(LL i=1;i<n;i<<=1)
{
LL gn = qpow(5LL , (Mod-1) / (i<<1) ,Mod);
for(LL j=0;j<n;j+=(i<<1))
{
LL g=1;
for(LL k=0;k<i;k++,g=(g*gn)%Mod)
{
LL x=a[j+k]; LL y=a[j+k+i]*g%Mod;
a[j+k] = (x+y)%Mod; a[j+k+i] = (x-y+Mod)%Mod;
}
}
}
if(fh==-1) reverse(a+1,a+n);
}
void NTT(LL *a,LL *b,LL n,LL m)
{
m+=n; LL l=0; for(n=1;n<=m;n<<=1) l++;
for(LL i=1;i<n;i++) R[i] = (R[i>>1]>>1) | ((i&1) << (l-1));
NFT(a,n,1); NFT(b,n,1);
for(LL i=0;i<n;i++) a[i] = (a[i]*b[i])%Mod;
NFT(a,n,-1); LL ny = qpow(n,Mod-2,Mod);
for(LL i=0;i<n;i++) a[i] = (a[i]*ny)%Mod;
}
LL a[N],b[N],c[N],n;
int main()
{
//check();
n=read(); len=0; memset(first,-1,sizeof(first));
for(LL i=1;i<n;i++){LL x=read(),y=read(); ins(x,y); ins(y,x);}
memset(siz,0,sizeof(siz)); dfs(1,0);
jc[0]=1; for(LL i=1;i<=n;i++) jc[i] = (jc[i-1] * i)%Mod;
for(LL i=0;i<=n;i++) a[i]=jc[i];
for(LL i=2;i<=n;i++) c[n]++,c[siz[i]]--,c[n-siz[i]]--; c[n]++;
for(LL i=0;i<=n;i++) a[i]=(a[i]*c[i]%Mod+Mod)%Mod,b[i]=qpow(jc[n-i],Mod-2,Mod);
//a[1]=1; a[2]=2;
//b[1]=1; b[2]=3;
NTT(a,b,n,n);
for(LL i=1;i<=n;i++) printf("%lld\n",a[n+i] * qpow(jc[i],Mod-2,Mod) % Mod);
return 0;
}
Submission Info
Submission Time |
|
Task |
A - STring |
User |
lzjzlj |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2574 Byte |
Status |
TLE |
Exec Time |
1055 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
0 / 200 |
0 / 100 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2 |
Subtask1 |
example0, example1, example2, sub_corner0, sub_corner1, sub_corner2, sub_rand0, handmade0, handmade1 |
All |
corner0, corner1, corner2, example0, example1, example2, handmade0, handmade1, maxrand0, sub_corner0, sub_corner1, sub_corner2, sub_rand0 |
Case Name |
Status |
Exec Time |
Memory |
corner0 |
TLE |
1055 ms |
256 KB |
corner1 |
TLE |
1055 ms |
256 KB |
corner2 |
TLE |
1055 ms |
256 KB |
example0 |
TLE |
1055 ms |
256 KB |
example1 |
TLE |
1055 ms |
256 KB |
example2 |
TLE |
1055 ms |
256 KB |
handmade0 |
TLE |
1055 ms |
256 KB |
handmade1 |
TLE |
1055 ms |
256 KB |
maxrand0 |
TLE |
1055 ms |
256 KB |
sub_corner0 |
TLE |
1055 ms |
256 KB |
sub_corner1 |
TLE |
1055 ms |
256 KB |
sub_corner2 |
TLE |
1055 ms |
256 KB |
sub_rand0 |
TLE |
1055 ms |
256 KB |