Submission #906824

---

Source Code Expand

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define sz(s) ((int) ((s).size()))
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif

typedef long long ll;
typedef long double ld;

const int inf = (int) 1e9 + 100;
const ld eps = 1e-11;
const ld PI = acos(-1.0L);

namespace FFT {
  struct comp {
    ld x, y;

    comp(ld x = 0, ld y = 0) : x(x), y(y) {}

    comp operator+(const comp & b) const {
      return comp(x + b.x, y + b.y);
    }

    comp operator-(const comp & b) const {
      return comp(x - b.x, y - b.y);
    }

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

  const int maxn = 1 << 20;
  int n, logn, rev[maxn];
  comp a[maxn], b[maxn];

  void init() {
    rev[0] = 0;
    for (int i = 1, j = -1; i < n; i++) {
      if (!(i & (i - 1))) {
        j++;
      }
      rev[i] = rev[i ^ (1 << j)] ^ (1 << (logn - 1 - j));
    }
  }

  void fft(comp * a, bool back = false) {
    for (int i = 0; i < n; i++) {
      if (rev[i] < i) {
        swap(a[rev[i]], a[i]);
      }
    }
    for (int j0 = 1; j0 < n; j0 <<= 1) {
      comp mult = comp(cos(PI / j0), sin(PI / j0));
      if (back) {
        mult.y = -mult.y;
      }
      for (int i = 0; i < n; i += j0) {
        comp cur = comp(1);
        for (int it = 0, j = i + j0; it < j0; i++, j++, it++) {
          comp add = a[j] * cur;
          a[j] = a[i] - add;
          a[i] = a[i] + add;

          cur = cur * mult;
        }
      }
    }
  }

  int mult(int n1, int * a1, int n2, int * a2, ll * ans) {
    for (n = 1, logn = 0; n < n1 + n2 - 1; n <<= 1, logn++) ;
    init();

    for (int i = 0; i < n; i++) {
      a[i] = (i < n1) ? a1[i] : 0;
      b[i] = (i < n2) ? a2[i] : 0;
    }
    fft(a);
    fft(b);
    for (int i = 0; i < n; i++) {
      a[i] = a[i] * b[i];
    }
    fft(a, true);

    int anslen = 0;
    for (int i = 0; i < n; i++) {
      ll cur = (ll) floor(a[i].x / n + 0.5);
      if (cur) {
        while (anslen < i) {
          ans[anslen++] = 0;
        }
        ans[anslen++] = cur;
      }
    }
    return anslen;
  }
}

mt19937 mrand(random_device{} ());
int rnd(int x) {
  return mrand() % x;
}

const int mod = 924844033;

void add(int & a, int b) {
  if ((a += b) >= mod) {
    a -= mod;
  }
}

int mult(int a, int b) {
  return (ll) a * b % mod;
}

int power(int a, int p) {
  int res = 1;
  while (p) {
    if (p & 1) {
      res = mult(res, a);
    }
    a = mult(a, a);
    p >>= 1;
  }
  return res;
}

int inv(int a) {
  return power(a, mod - 2);
}

int n;
const int maxn = 2e5 + 100;
int fact[maxn];

void precalc() {
  fact[0] = 1;
  for (int i = 1; i < maxn; i++) {
    fact[i] = mult(fact[i - 1], i);
  }
}

vector<vector<int> > tree;
int cnt[maxn];

bool read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  tree = vector<vector<int> > (n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--, b--;
    tree[a].pb(b);
    tree[b].pb(a);
  }
  return true;
}

int a[maxn];

void dfs(int v, int par = -1) {
  a[n]++;
  cnt[v] = 1;
  for (int i = 0; i < sz(tree[v]); i++) {
    int to = tree[v][i];
    if (to == par) {
      continue;
    }
    dfs(to, v);
    cnt[v] += cnt[to];
    a[cnt[to]]--;
  }
  a[n - cnt[v]]--;
}

int f1[maxn], f2[maxn], ans[maxn * 2];
int tmpa[maxn], tmpb[maxn];
ll tmpans[maxn * 2];

const int BASE = 1000;

int getmy(int i, int val) {
  for (int j = 0; j < i; j++) {
    val /= BASE;
  }
  return val % BASE;
}

void mymult() {
  int m = n + 1;
  memset(ans, 0, sizeof(ans));
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < m; k++) {
        tmpa[k] = getmy(i, f1[k]);
        tmpb[k] = getmy(j, f2[k]);
      }
      int res = FFT::mult(m, tmpa, m, tmpb, tmpans);
      int tomult = power(BASE, i + j);
      for (int r = 0; r < res; r++) {
        add(ans[r], mult(tomult, tmpans[r] % mod));
      }
    }
  }
}

void solve() {
  memset(a, 0, sizeof(a));
  memset(f1, 0, sizeof(f1));
  memset(f2, 0, sizeof(f2));
  dfs(0);
  for (int i = 0; i <= n; i++) {
    f1[i] = mult(fact[i], (a[i] + mod) % mod);
    f2[i] = inv(fact[n - i]);
  }
  mymult();
  for (int i = 1; i <= n; i++) {
    printf("%d\n", mult(ans[i + n], inv(fact[i])));
  }
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen("text.in", "r", stdin));
  assert(freopen("text.out", "w", stdout));
#endif

  while (true) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time: %.18f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘bool read()’:
./Main.cpp:167:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &a, &b);
                          ^

Judge Result