Submission #1680443


Source Code Expand

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int MAXN = 524300;
const int mo = 924844033;
const int g = 5;

int N,L;
int a[MAXN],b[MAXN],mi[MAXN];
int n;
int cnt[MAXN];
int inv[MAXN],js[MAXN];
struct edge{
	int x,nxt;
}e[MAXN];
int h[MAXN],tot;
int bitr[MAXN];
int siz[MAXN];
LL ny;

LL quickmi(LL x,LL tim){LL ans=1;x%=mo;for(;tim;tim/=2,x=x*x%mo)if (tim&1)ans=ans*x%mo;return ans;}

void inse(int x,int y){e[++tot].x=y;e[tot].nxt=h[x];h[x]=tot;}

void prepare(){
	inv[0]=inv[1]=1;
	fo(i,2,n)inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;
	fo(i,1,n)inv[i]=1ll*inv[i]*inv[i-1]%mo;
	js[0]=js[1]=1;
	fo(i,1,n)js[i]=js[i-1]*i%mo;
	N=1,L=0;
	while(N<=n*2)N<<=1,L++;
	fo(i,0,N-1){
		bitr[i]=0;
		fo(j,0,L-1)
		if (((1<<j)&i)>0)bitr[i]+=(1<<(L-1-j));
	}
	LL G=quickmi(g,(mo-1)/N);
	mi[0]=1;
	fo(i,1,N)mi[i]=mi[i-1]*G%mo;
	ny=quickmi(N,mo-2);
}

void dfs(int x){
	siz[x]=1;
	for(int p=h[x];p;p=e[p].nxt)
	if (!siz[e[p].x]){
		dfs(e[p].x);
		siz[x]+=siz[e[p].x];
	}
	if (x>1){
		cnt[siz[x]]++;
		cnt[n-siz[x]]++;
	}
}

LL calc(int n,int m){return 1ll*js[n]*inv[m]%mo*inv[n-m]%mo;}

LL add(LL x,LL y){return x+y>=mo?x+y-mo:x+y;}

LL dec(LL x,LL y){return x>=y?x-y:x+mo-y;}

void DFT(int *a){
	fo(i,0,N-1)
	if (i<bitr[i])swap(a[i],a[bitr[i]]);
	for(int now=2;now<=N;now<<=1){
		int half=now/2;
		fo(i,0,half-1){
			LL w=mi[N/now*i];
			for(int j=i;j<N;j+=now){
				LL l=a[j],r=w*a[j+half]%mo;
				a[j]=add(l,r);
				a[j+half]=dec(l,r);
			}
		}
	}
}

void IDFT(int *a){
	fo(i,0,N-1)
	if (i<bitr[i])swap(a[i],a[bitr[i]]);
	for(int now=2;now<=N;now<<=1){
		int half=now/2;
		fo(i,0,half-1){
			LL w=mi[N-N/now*i];
			for(int j=i;j<N;j+=now){
				LL l=a[j],r=w*a[j+half]%mo;
				a[j]=add(l,r);
				a[j+half]=dec(l,r);
			}
		}
	}
	fo(i,0,N-1)a[i]=ny*a[i]%mo;
}

void ntt(int *a,int *b){
	DFT(a);DFT(b);
	fo(i,0,N-1)a[i]=1ll*a[i]*b[i]%mo;
	IDFT(a);
}

int main(){
	n=get();
	fo(i,2,n){
		int x=get(),y=get();
		inse(x,y),inse(y,x);
	}
	prepare();
	dfs(1);
	fo(i,0,n)a[n-i]=1ll*cnt[i]*js[i]%mo;
	fo(i,0,n)b[i]=inv[i];
	ntt(a,b);
	fo(i,0,n/2)swap(a[i],a[n-i]);
	fo(i,1,n){
		LL v=1ll*a[i]*inv[i]%mo;
		v=(1ll*calc(n,i)*n%mo+mo-v)%mo;
		printf("%lld\n",v);
	}
	return 0;
}

Submission Info

Submission Time
Task F - Many Easy Problems
User samjia2000
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2776 Byte
Status WA
Exec Time 307 ms
Memory 28800 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1900
Status
AC × 3
AC × 3
WA × 45
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 WA 279 ms 23552 KB
doublestar1 WA 280 ms 23552 KB
doublestar2 WA 277 ms 23424 KB
doublestar3 WA 288 ms 23552 KB
doublestar4 WA 277 ms 23424 KB
example0 AC 7 ms 18688 KB
example1 AC 6 ms 18688 KB
example2 AC 7 ms 18688 KB
line0 WA 304 ms 28672 KB
line1 WA 306 ms 28800 KB
line2 WA 306 ms 28800 KB
line3 WA 304 ms 28672 KB
line4 WA 307 ms 28800 KB
maxrand0 WA 303 ms 23552 KB
maxrand1 WA 302 ms 23552 KB
maxrand10 WA 301 ms 23552 KB
maxrand11 WA 301 ms 23552 KB
maxrand12 WA 305 ms 23552 KB
maxrand13 WA 301 ms 23552 KB
maxrand14 WA 302 ms 23552 KB
maxrand15 WA 303 ms 23552 KB
maxrand16 WA 301 ms 23552 KB
maxrand17 WA 300 ms 23552 KB
maxrand18 WA 300 ms 23552 KB
maxrand19 WA 302 ms 23552 KB
maxrand2 WA 301 ms 23552 KB
maxrand3 WA 301 ms 23552 KB
maxrand4 WA 302 ms 23552 KB
maxrand5 WA 304 ms 23552 KB
maxrand6 WA 302 ms 23552 KB
maxrand7 WA 301 ms 23552 KB
maxrand8 WA 301 ms 23552 KB
maxrand9 WA 301 ms 23552 KB
rand0 WA 9 ms 18688 KB
rand1 WA 6 ms 18688 KB
rand2 WA 8 ms 18688 KB
rand3 WA 9 ms 18688 KB
rand4 WA 7 ms 18688 KB
rand5 WA 9 ms 18688 KB
rand6 WA 8 ms 18688 KB
rand7 WA 9 ms 18688 KB
rand8 WA 7 ms 18688 KB
rand9 WA 8 ms 18688 KB
star0 WA 274 ms 23552 KB
star1 WA 273 ms 23424 KB
star2 WA 275 ms 23552 KB
star3 WA 273 ms 23424 KB
star4 WA 274 ms 23552 KB