Submission #905900


Source Code Expand

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

const int maxL = 18;
const int maxN = 1 << maxL;
const long long mod = 924844033;
long long generator = 5;
long long root[maxN], invroot[maxN];
long long inv[maxN], fact[maxN], ifact[maxN];
int rev[maxL+1][maxN];

inline long long add(long long a, long long b)
{
	a += b;
	if (a >= mod)
		a -= mod;
	return a;
}

inline long long mul(long long a, long long b)
{
	return a * b % mod;
}

long long fpow(long long a, long long p)
{
	a %= mod;
	p = (p % (mod - 1) + mod - 1) % (mod - 1);
	long long r = 1;
	while (p){
		if (p & 1) r = r * a % mod;
		a = a * a % mod;
		p >>= 1;
	}
	return r;
}

int get_rev(int a, int u)
{
	int r = 0;
	u--;
	while (u){
		r <<= 1;
		r += a & 1;
		a >>= 1;
		u >>= 1;
	}
	return r;
}

void init()
{
	root[0] = invroot[0] = 1;
	root[1] = fpow(generator, (mod - 1) / maxN);
	invroot[1] = fpow(root[1], -1);
	for (int j = 2; j<maxN; j++){
		root[j] = mul(root[j - 1], root[1]);
		invroot[j] = mul(invroot[j - 1], invroot[1]);
	}
	for (int l=0;l<=maxL;l++){
		for (int i=0;i<(1<<l);i++) rev[l][i] = get_rev(i,(1<<l));
	}

	inv[1] = fact[0] = fact[1] = ifact[0] = ifact[1] = 1;
	for (int i=2;i<maxN;i++){
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
		fact[i] = fact[i-1] * i % mod;
		ifact[i] = ifact[i-1] * inv[i] % mod;
	}
}

long long comb(int n, int k)
{
	if (n < 0 || k < 0 || k > n) return 0;
	return fact[n] * ifact[k] % mod * ifact[n-k] % mod;
}
vector<long long> fft(long long *root, int *rev, vector<long long> input)
{
	int n = input.size();
	vector<long long> res(n);
	for (int i = 0; i < n; i++) res[rev[i]] = input[i];
	for (int i = 2, h = 1, u = maxN >> 1; i <= n; i <<= 1, h <<= 1, u >>= 1){
		for (int k = 0; k < n; k += i){
			for (int j = 0; j < h; j++){
				long long w = root[u*j];
				long long t = mul(w, res[k + j + h]);
				long long u = res[k + j];
				res[k + j] = add(u, t);
				res[k + j + h] = add(u, mod - t);
			}
		}
	}
	return res;
}

void poly_norm(vector<long long> &a)
{
	while (!a.empty() && a.back() == 0) a.pop_back();
}

vector<long long> poly_mul(vector<long long> a, vector<long long> b)
{
	vector<long long> c;
	int al = a.size(), bl = b.size(), n = 1, l = 0;
	while (n < al + bl - 1) n *= 2, l++;
	if (n <= 32){
		c = vector<long long>(n,0);
		for (int i=0;i<al;i++) for (int j=0;j<bl;j++) c[i+j] = (c[i+j] + a[i] * b[j]) % mod;
	}
	else{
		a.resize(n); b.resize(n);
		vector<long long> A = fft(root,rev[l],a);
		vector<long long> B = fft(root,rev[l],b);
		for (int i=0;i<n;i++) A[i] = mul(A[i],B[i]);
		c = fft(invroot,rev[l],A);
		long long invn = fpow(n,-1);
		for (int i=0;i<n;i++) c[i] = mul(c[i],invn);
	}
	c.resize(al+bl-1);
	return c;
}

vector<int> v[200020];
vector<int> sz;

int dfs(int x, int l)
{
	int s = 1;
	for (int y : v[x]) if (y != l) s += dfs(y,x);
	if (l) sz.push_back(s);
	return s;
}

vector<long long> go(vector<int> sz, int div)
{
	if (sz.empty()) return vector<long long>();
	if (div == -1) return vector<long long>(1,sz.size());

	vector<int> a,b;
	for (int x : sz){
		if (x < (1 << div)) a.push_back(x);
		else b.push_back(x-(1<<div));
	}

	vector<long long> p = go(a,div-1); poly_norm(p);
	vector<long long> q = go(b,div-1); poly_norm(q);
	if (!q.empty()){
		vector<long long> r((1<<div)+1,0);
		for (int k=0;k<=(1<<div);k++){
			r[k] = comb((1<<div),k);
		}
		q = poly_mul(q,r);
	}

	p.resize(max(p.size(),q.size()));
	for (int i=0;i<q.size();i++){
		p[i] = add(p[i],q[i]);
	}

	return p;
}

int main()
{
	init();

	int n; scanf ("%d",&n);
	for (int i=1;i<n;i++){
		int a,b; scanf ("%d %d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1,0);
	for (int i=0;i<n-1;i++) sz.push_back(n-sz[i]);

	vector<long long> v(n+1,0);
	for (int i=0;i<=n;i++) v[i] = comb(n,i) * n % mod;
	vector<long long> u = go(sz,17);
	u.resize(n+1);

	for (int i=1;i<=n;i++) printf ("%lld\n",(v[i]+mod-u[i])%mod);

	return 0;
}

Submission Info

Submission Time
Task F - Many Easy Problems
User august14
Language C++14 (GCC 5.4.1)
Score 1900
Code Size 4081 Byte
Status AC
Exec Time 744 ms
Memory 59064 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:169:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf ("%d",&n);
                        ^
./Main.cpp:171:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int a,b; scanf ("%d %d",&a,&b);
                                 ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1900 / 1900
Status
AC × 3
AC × 48
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 296 ms 57072 KB
doublestar1 AC 299 ms 57072 KB
doublestar2 AC 299 ms 58060 KB
doublestar3 AC 303 ms 57740 KB
doublestar4 AC 302 ms 57072 KB
example0 AC 34 ms 17280 KB
example1 AC 34 ms 17280 KB
example2 AC 33 ms 17280 KB
line0 AC 739 ms 57196 KB
line1 AC 737 ms 56244 KB
line2 AC 743 ms 57244 KB
line3 AC 741 ms 57232 KB
line4 AC 744 ms 57168 KB
maxrand0 AC 494 ms 58196 KB
maxrand1 AC 486 ms 58164 KB
maxrand10 AC 486 ms 58148 KB
maxrand11 AC 501 ms 58260 KB
maxrand12 AC 537 ms 58180 KB
maxrand13 AC 485 ms 58076 KB
maxrand14 AC 498 ms 58160 KB
maxrand15 AC 502 ms 58300 KB
maxrand16 AC 498 ms 58200 KB
maxrand17 AC 447 ms 57904 KB
maxrand18 AC 487 ms 58216 KB
maxrand19 AC 538 ms 58232 KB
maxrand2 AC 493 ms 58184 KB
maxrand3 AC 493 ms 58348 KB
maxrand4 AC 487 ms 58244 KB
maxrand5 AC 503 ms 58128 KB
maxrand6 AC 437 ms 57940 KB
maxrand7 AC 493 ms 58280 KB
maxrand8 AC 504 ms 58164 KB
maxrand9 AC 508 ms 58244 KB
rand0 AC 38 ms 18072 KB
rand1 AC 34 ms 17280 KB
rand2 AC 37 ms 17792 KB
rand3 AC 38 ms 18048 KB
rand4 AC 35 ms 17536 KB
rand5 AC 38 ms 18080 KB
rand6 AC 37 ms 17792 KB
rand7 AC 38 ms 18080 KB
rand8 AC 34 ms 17408 KB
rand9 AC 35 ms 17664 KB
star0 AC 299 ms 58992 KB
star1 AC 300 ms 58888 KB
star2 AC 302 ms 59064 KB
star3 AC 302 ms 58992 KB
star4 AC 301 ms 59000 KB