Submission #905104

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=924844033;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int M=201000;
int sz[M],coef[M],n,u,v;
VI e[M];
void dfs(int u,int f) {
	sz[u]=1;
	for (auto v:e[u]) {
		if (v==f) continue;
		dfs(v,u);
		coef[sz[v]]--;
		sz[u]+=sz[v];
	}
	coef[n-sz[u]]--;
	coef[n]++;
}
const int max0=500000;

int N,L;
struct comp
{
	double x, y;

	comp(): x(0), y(0) { }
	comp(const double &_x, const double &_y): x(_x), y(_y) { }

};

inline comp operator+(const comp &a, const comp &b) { return comp(a.x + b.x, a.y + b.y); }
inline comp operator-(const comp &a, const comp &b) { return comp(a.x - b.x, a.y - b.y); }
inline comp operator*(const comp &a, const comp &b) { return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
inline comp conj(const comp &a) { return comp(a.x, -a.y); }

const double PI = acos(-1);

comp w[max0 + 5];
int bitrev[max0 + 5];

void fft(comp *a, const int &n) {
	rep(i, 0, n) if (i < bitrev[i]) swap(a[i], a[bitrev[i]]);
	for (int i = 2, lyc = n >> 1; i <= n; i <<= 1, lyc >>= 1)
		for (int j = 0; j < n; j += i)
		{
			comp *l = a + j, *r = a + j + (i >> 1), *p = w;
			rep(k, 0, i >> 1)
			{
				comp tmp = *r * *p;
				*r = *l - tmp, *l = *l + tmp;
				++l, ++r, p += lyc;
			}
		}
}

inline void fft_prepare()
{
	rep(i, 0, N) bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (L - 1));
	rep(i, 0, N) w[i] = comp(cos(2 * PI * i / N), sin(2 * PI * i / N));
}

static comp a[max0 + 5], b[max0 + 5];
static comp ad[max0 + 5], bd[max0 + 5];

inline void conv(int *x, int *y, int *z,int K) {
	N = (K + 1) << 1;
	L = 0;
	while ((1 << L) < N) ++L;
	N = 1 << L;
	fft_prepare();
	rep(i, 0, K + 1) a[i] = comp(x[i] & 32767, x[i] >> 15);
	rep(i, 0, K + 1) b[i] = comp(y[i] & 32767, y[i] >> 15);
	rep(i, K + 1, N) a[i] = b[i] = comp(0, 0);
	fft(a, N), fft(b, N);
	rep(i, 0, N)
	{
		int j = (N - i) & (N - 1);
		static comp da, db, dc, dd;
		da = (a[i] + conj(a[j])) * comp(0.5, 0);
		db = (a[i] - conj(a[j])) * comp(0, -0.5);
		dc = (b[i] + conj(b[j])) * comp(0.5, 0);
		dd = (b[i] - conj(b[j])) * comp(0, -0.5);
		ad[j] = da*dc+da*dd*comp(0,1);
		bd[j] = db*dc+db*dd*comp(0,1);
	}
	rep(i, 0, N) {
		a[i] = ad[i];
	}
	rep(i, 0, N) b[i] = bd[i];
	fft(a, N), fft(b, N);
	rep(i, 0, N)
	{
		int da = (ll)(a[i].x / N + 0.5) % mod;
		int db = (ll)(a[i].y / N + 0.5) % mod;
		int dc = (ll)(b[i].x / N + 0.5) % mod;
		int dd = (ll)(b[i].y / N + 0.5) % mod;
		z[i] = (da + ((ll)(db + dc) << 15) + ((ll)dd << 30)) % mod;
	}
}

int p[max0],q[max0],r[max0],fnv[M];
int main() {
	scanf("%d",&n);
	rep(i,1,n) {
		scanf("%d%d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	dfs(1,0);
	p[0]=1;
	rep(i,1,n+1) p[i]=(ll)p[i-1]*i%mod;
	rep(i,0,n+1) fnv[i]=powmod(p[i],mod-2),q[i]=fnv[i];
	rep(i,0,n+1) {
		p[i]=(ll)p[i]*coef[i]%mod;
		if (p[i]<0) p[i]+=mod;
	}
	reverse(q,q+n+1);
	conv(p,q,r,n+1);
	rep(i,1,n+1) {
		int v=r[n+i];
		v=(ll)v*fnv[i]%mod;
		printf("%d\n",v);
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:124:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:126:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
                      ^

Judge Result