Submission #907592

---

Source Code Expand

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

mt19937 mrand(random_device{} ()); 

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

typedef long double ld;
typedef long long ll;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);

const int mod = 924844033;
void add(int &x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int mult(int x, int y) {
  return (long long) x * y % mod;
}

int myPower(int x, int pw) {
  int res = 1;
  for (; pw; pw >>= 1) {
    if (pw & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
  }
  return res;
}

const int maxn = (int) 2e5 + 10;
int inv[maxn];

void precalc() {
  for (int i = 1; i < maxn; ++i) {
    inv[i] = myPower(i, mod - 2);
  }
}

//BEGIN ALGO
namespace FFT {
  struct com {
    ld x, y;

    com(ld _x = 0, ld _y = 0) : x(_x), y(_y) {}

    inline com operator + (const com &c) const {
      return com(x + c.x, y + c.y);
    }
    inline com operator - (const com &c) const {
      return com(x - c.x, y - c.y);
    }
    inline com operator * (const com &c) const {
      return com(x * c.x - y * c.y, x * c.y + y * c.x);
    }
    inline com conj() const {
      return com(x, -y);
    }
  };

  const static int maxk = 20, maxn = (1 << maxk) + 1;
  int dp[maxn];
  com rs[maxn];
  int n, k;
  int lastk = -1;

  void fft(com *a, bool torev = 0) {
    if (lastk != k) {
      lastk = k;
      dp[0] = 0;
      for (int i = 1, g = -1; i < n; ++i) {
        if (!(i & (i - 1))) {
          ++g;
        }
        dp[i] = dp[i ^ (1 << g)] ^ (1 << (k - 1 - g));
      }
    }
    for (int i = 0; i < n; ++i) {
      if (i < dp[i]) {
        swap(a[i], a[dp[i]]);
      }
    }
    for (int len = 1; len < n; len <<= 1) {
      ld alf = pi / len;
      com w(cos(alf), sin(alf));
      if (torev) {
        w.y = -w.y;
      }
      for (int i = 0; i < n; i += len) {
        com cw(1, 0);
        for (int it = 0, j = i + len; it < len; ++it, ++i, ++j) {
          com tmp = a[j] * cw;
          a[j] = a[i] - tmp;
          a[i] = a[i] + tmp;
          cw = cw * w;
        }
      }
    }
  }

  com a[maxn];
  int mult(int na, int *_a, int nb, int *_b, long long *ans) {
    if (!na || !nb) {
      return 0;
    }
    for (k = 0, n = 1; n < na + nb - 1; n <<= 1, ++k) ;
    assert(n < maxn);
    for (int i = 0; i < n; ++i) {
      a[i] = com(i < na ? _a[i] : 0, i < nb ? _b[i] : 0);
    }
    fft(a);
    a[n] = a[0];
    for (int i = 0; i <= n - i; ++i) {
      a[i] = (a[i] * a[i] - (a[n - i] * a[n - i]).conj()) * com(0, (ld) -1 / n / 4);
      a[n - i] = a[i].conj();
    }
    fft(a, 1);
    int res = 0;
    for (int i = 0; i < n; ++i) {
      long long val = (long long) round(a[i].x);
      //assert(abs(val - a[i].x) < 1e-1);
      if (val) {
        assert(i < na + nb - 1);
        while (res < i) {
          ans[res++] = 0;
        }
        ans[res++] = val;
      }
    }
    return res;
  }
};
//END ALGO

int ta[maxn], tb[maxn];
long long tans[maxn];

void mult(int n1, int *a1, int n2, int *a2, int *ans) {
  for (int i = 0; i < n1 + n2 - 1; ++i) {
    ans[i] = 0;
  }
  const int Base = (int) 4e4;
  for (int it1 = 0; it1 < 2; ++it1) {
    int cur = !it1 ? 1 : Base;
    for (int it2 = 0; it2 < 2; ++it2) {
      for (int i = 0; i < n1; ++i) {
        ta[i] = !it1 ? (a1[i] % Base) : (a1[i] / Base);
      }
      for (int i = 0; i < n2; ++i) {
        tb[i] = !it2 ? (a2[i] % Base) : (a2[i] / Base);
      }
      int res = FFT::mult(n1, ta, n2, tb, tans);
      for (int i = 0; i < res; ++i) {
        ans[i] = (tans[i] % mod * cur + ans[i]) % mod;
      }
      cur *= Base;
    }
  }
  assert(n1 > 0 && n2 > 0);
#ifdef DEBUG
  /*for (int i = 0; i < n1; ++i) {
    eprintf("%d%c", a1[i], " \n"[i == n1 - 1]);
  }
  for (int i = 0; i < n2; ++i) {
    eprintf("%d%c", a2[i], " \n"[i == n2 - 1]);
  }*/
  for (int i = 0; i < n1 + n2 - 1; ++i) {
    int res = 0;
    for (int j = 0; j < n1 && j <= i; ++j) {
      int k = i - j;
      if (k >= n2) {
        continue;
      }
      add(res, mult(a1[j], a2[k]));
    }
    //eprintf("ans[%d] = %d\n", i, ans[i]);
    //eprintf("res = %d\n", res);
    //ans[i] = res;
    assert(ans[i] == res);
  }
  /*
  for (int i = 0; i < n1 + n2 - 1; ++i) {
    eprintf("%d%c", ans[i], " \n"[i == n2 - 1]);
  }*/
#endif
}


vector<vector<int> > es;

int n;

int read() {
  if (scanf("%d", &n) < 1) {
    return 0;
  }
  es = vector<vector<int> >(n);
  for (int i = 0; i < n - 1; ++i) {
    int s, t;
    scanf("%d%d", &s, &t);
    --s, --t;
    es[s].pb(t), es[t].pb(s);
  }
  return 1;
}

int a[maxn];

int dfs(int v, int pr) {
  int res = 1;
  for (int u : es[v]) {
    if (u == pr) {
      continue;
    }
    int got = dfs(u, v);
    add(a[got], mod - 1);
    res += got;
  }
  if (pr != -1) {
    add(a[n - res], mod - 1);
  }
  return res;
}

int ans[maxn];

int coefs[maxn];

int tmp[maxn];

void solve(int l, int r) {
  if (l + 1 == r) {
    ans[l] = a[l];
    return;
  }

  int m = (l + r) / 2;
  solve(l, m);
  solve(m, r);
  {
    int t = m - l;

    int curc = 1;
    coefs[0] = 1;
    for (int i = 1; i <= t; ++i) {
      coefs[i] = mult(coefs[i - 1], mult(t - i + 1, inv[i]));
    }
  }
  mult(r - m, ans + m, m - l + 1, coefs, tmp);
  for (int i = l; i < m; ++i) {
    add(tmp[i - l], ans[i]);
  }
  /*for (int i = l; i < r; ++i) {
    eprintf("%d%c", ans[i], " \n"[i == r - 1]);
  }
  eprintf("solve [%d..%d):\n", l, r);*/
  for (int i = l; i < r; ++i) {
    ans[i] = tmp[i - l];
    //eprintf("%d%c", ans[i], " \n"[i == r - 1]);
  }
}

void solve() {
  for (int i = 0; i <= n; ++i) {
    a[i] = 0;
  }
  a[n] = n;
  dfs(0, -1);
  /*for (int i = 0; i <= n; ++i) {
    eprintf("%d%c", a[i], " \n"[i == n]);
  }*/
  solve(0, n + 1);
  for (int i = 1; i <= n; ++i) {
    printf("%d\n", ans[i]);
  }
}

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

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

Submission Info

Compile Error

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

Judge Result