Submission #1680611

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 1 << 19, MOD = 924844033, G = 5;
typedef long long i64;

class Edge {
public:
  int nxt, to;
} e[MAX_N << 1];

int head[MAX_N], cnt;
void addedge(int u, int v) {
  e[++cnt] = (Edge){head[u], v}, head[u] = cnt;
  e[++cnt] = (Edge){head[v], u}, head[v] = cnt;
}

int N, sz[MAX_N];
i64 val[MAX_N];

void dfs(int u, int v) {
  sz[u] = 1, val[N]++;
  for (int i = head[u]; i; i = e[i].nxt)
    if (e[i].to != v) {
      dfs(e[i].to, u);
      sz[u] += sz[e[i].to];
      val[sz[e[i].to]]--;
    }
  val[N - sz[u]]--;
}

void rader(i64 *y, int len) {
  for (int i = 1, j = len >> 1; i < len - 1; ++i) {
    if (i < j) swap(y[i], y[j]);
    int k = len >> 1;
    while (j >= k) {
      j -= k;
      k >>= 1;
    }
    if (j < k) j += k;
  }
}

i64 fpm(i64 x, i64 y) {
  i64 res = 1;
  while (y) {
    if (y & 1) res = res * x % MOD;
    x = x * x % MOD;
    y >>= 1;
  }
  return res;
}

void DFT(i64 *y, int len, int op) {
  rader(y, len);
  for (int h = 2; h <= len; h <<= 1) {
    i64 wn;
    if (op == 1) wn = fpm(G, (MOD - 1) / h);
    else wn = fpm(G, MOD - 1 - (MOD - 1) / h);

    for (int j = 0; j < len; j += h) {
      int l = h >> 1;
      i64 w = 1;
      for (int k = j; k < j + l; ++k) {
	i64 u = y[k], v = y[k + l] * w % MOD;
	y[k] = (u + v) % MOD, y[k + l] = (u - v) % MOD;
	w = w * wn % MOD;
      }
    }
  }
  if (op == -1) {
    i64 INV = fpm(len, MOD - 2);
    for (int i = 0; i < len; ++i)
      y[i] = y[i] * INV % MOD;
  }
}

i64 fac[MAX_N], ifac[MAX_N], inv[MAX_N];

int main() {
  scanf("%d", &N);
  for (int i = 1, u, v; i < N; ++i) {
    scanf("%d%d", &u, &v);
    addedge(u, v);
  }

  int len = 1;
  while (len <= N + N) len <<= 1;
  
  dfs(1, 0);
  fac[0] = ifac[0] = inv[1] = 1;
  for (int i = 1; i <= N; ++i) fac[i] = fac[i - 1] * i % MOD;
  for (int i = 2; i <= N; ++i) inv[i] = -(MOD / i) * inv[MOD % i] % MOD;
  for (int i = 1; i <= N; ++i) ifac[i] = ifac[i - 1] * inv[i] % MOD;

  static i64 B[MAX_N];
  for (int i = 1; i <= N; ++i) val[i] = val[i] * fac[i] % MOD;
  for (int i = 1; i <= N; ++i) B[i] = ifac[N - i];

  DFT(val, len, 1), DFT(B, len, 1);
  for (int i = 0; i < len; ++i)
    B[i] = val[i] * B[i] % MOD;
  DFT(B, len, -1);

  for (int i = 1; i <= N; ++i) {
    i64 result = B[i + N] * ifac[i] % MOD;
    printf("%lld\n", (result + MOD) % MOD);
  }
  
  return 0;
}

Submission Info

Compile Error

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

Judge Result