Submission #1807617


Source Code Expand

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define next nex
using namespace std;
const int MAXN = 524290;
const int MOD = 924844033;
int a[MAXN], b[MAXN];
int n, m, i, j, k, x, y;
int size[MAXN];
int first[MAXN], next[MAXN], go[MAXN], t, pre[MAXN];
int bit[MAXN], f[MAXN];
inline int get()
{
	char c;
	while ((c = getchar()) < 48 || c > 57);
	int res = c - 48;
	while ((c = getchar()) >= 48 && c <= 57)
		res = res * 10 + c - 48;
	return res;
}
inline void add(int x, int y)
{
	next[++t] = first[x]; first[x] = t; go[t] = y;
}
inline void dfs(int now, int las)
{
	size[now] = 1;
	for(int i = first[now]; i; i = next[i])
		if (go[i] != las) dfs(go[i], now), size[now] += size[go[i]];
	a[n - size[now]] --;
	a[n] ++;
	for(int i = first[now]; i; i = next[i])
		if (go[i] != las) a[size[go[i]]] --;
}
inline int ksm(int x, int y, int z)
{
	int b = 1;
	while (y)
	{
		if (y & 1) b = 1ll * b * x % z;
		x = 1ll * x * x % z;
		y >>= 1;
	}
	return b;
}
inline int ntt_init(int m)
{
	int n = 1, nn = 0;
	while (n <= m) n <<= 1, nn ++;
	int g = ksm(5, (MOD - 1) / n, MOD);
	f[0] = 1;
	for(int i = 1; i < n; i ++)
		f[i] = 1ll * f[i - 1] * g % MOD, bit[i] = (bit[i >> 1] >> 1) | ((i & 1) << nn - 1);
	return nn;
}
inline void ntt(int *a, int nn, int ty)
{
	int n = 1 << nn;
	for(int i = 0; i < n; i ++)
		if (i < bit[i]) swap(a[i], a[bit[i]]);
	for(int k = 1; k <= nn; k ++)
	{
		int len = 1 << k, wn = (ty == 1) ? f[n / len] : f[n - n / len];
		for(int j = 0; j < n; j += len)
		{
			int m = len >> 1, w = 1;
			for(int i = j; i < j + m; i ++)
			{
				int l = a[i], t = 1ll * a[i + m] * w % MOD;
				a[i] = (l + t) % MOD;
				a[i + m] = (l - t + MOD) % MOD;
				w = 1ll * w * wn % MOD;
			}
		}
	}
}
int main()
{
	cin >> n;
	for(i = 1; i < n; i ++)
	{
		x = get(); y = get();
		add(x, y);
		add(y, x);
	}
	int nn = ntt_init(n << 1), N = 1 << nn;
	dfs(1, 0);
	for(i = 1; i <= n; i ++)
		if (a[i] < 0) a[i] += MOD;
	pre[0] = 1;
	for(i = 1; i < N; i ++)
		pre[i] = 1ll * pre[i - 1] * i % MOD, a[i] = 1ll * a[i] * pre[i] % MOD;
	for(i = 0; i <= n; i ++)
		b[i] = ksm(pre[n - i], MOD - 2, MOD);
	ntt(a, nn, 1);
	ntt(b, nn, 1);
	for(i = 0; i < N; i ++)
		a[i] = 1ll * a[i] * b[i] % MOD;
	ntt(a, nn, -1);
	int po = ksm(N, MOD - 2, MOD);
	for(i = 0; i < N; i ++)
		a[i] = 1ll * a[i] * po % MOD;
	for(i = n + 1; i <= n + n; i ++)
		printf("%d\n", 1ll * a[i] * ksm(pre[i - n], MOD - 2, MOD) % MOD);
}

Submission Info

Submission Time
Task A - STring
User diaosipan
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2553 Byte
Status WA
Exec Time 3 ms
Memory 8448 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:108:66: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
   printf("%d\n", 1ll * a[i] * ksm(pre[i - n], MOD - 2, MOD) % MOD);
                                                                  ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 100
Status
WA × 3
WA × 9
WA × 13
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 WA 3 ms 8448 KB
corner1 WA 3 ms 8448 KB
corner2 WA 3 ms 8448 KB
example0 WA 3 ms 8448 KB
example1 WA 3 ms 8448 KB
example2 WA 3 ms 8448 KB
handmade0 WA 3 ms 8448 KB
handmade1 WA 3 ms 8448 KB
maxrand0 WA 3 ms 8448 KB
sub_corner0 WA 3 ms 8448 KB
sub_corner1 WA 3 ms 8448 KB
sub_corner2 WA 3 ms 8448 KB
sub_rand0 WA 3 ms 8448 KB