Submission #905912

---

Source Code Expand

#include <memory.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

const int md = 924844033;
const int gen = 5;

int pw(int a, int b) {
  int x = 1, step = 1 << 30;
  while (step > 0) {
    x = (long long)x * x % md;
    if (step & b) x = (long long)x * a % md;
    step >>= 1;
  }
  return x;
}

void fft(vector <int> &a) {
  int n = a.size();
  for (int i = 0; i < n; i++) {
    int j = 0;
    int x = i, y = n - 1;
    while (y > 0) {
      j = (j << 1) + (x & 1);
      x >>= 1;
      y >>= 1;
    }
    if (i < j) swap(a[i], a[j]);
  }
  for (int len = 1; len < n; len *= 2) {
    int root = pw(gen, (md - 1) / (2 * len));
    for (int i = 0; i < n; i += 2 * len) {
      int w = 1;
      for (int j = 0; j < len; j++) {
        int u = a[i + j];
        int v = (long long)a[i + j + len] * w % md;
        a[i + j] = u + v;
        if (a[i + j] >= md) a[i + j] -= md;
        a[i + j + len] = u - v;
        if (a[i + j + len] < 0) a[i + j + len] += md;
        w = (long long)w * root % md;
      }
    }
  }
}

vector <int> multiply(vector <int> a, vector <int> b) {
  int an = a.size();
  int bn = b.size();
  int need = an + bn - 1;
  int nn = 1;
  while (nn < 2 * an || nn < 2 * bn) nn <<= 1;
  a.resize(nn);
  b.resize(nn);
  fft(a);
  fft(b);
  for (int i = 0; i < nn; i++) a[i] = (long long)a[i] * b[i] % md;
  reverse(++a.begin(), a.end());
  fft(a);
  int inv = pw(nn, md - 2);
  for (int i = 0; i < nn; i++) a[i] = (long long)a[i] * inv % md;
  a.resize(need);
  return a;
}

const int N = 1 << 19;

int fact[N], invfact[N];

int C(int n, int k) {
  if (n < 0 || k < 0 || k > n) return 0;
  int ans = fact[n];
  ans = (long long)ans * invfact[k] % md;
  ans = (long long)ans * invfact[n - k] % md;
  return ans;
}

vector <int> g[N];
int cnt[N];
int n;

int dfs(int v, int pr) {
  int sz = g[v].size();
  int res = 1;
  for (int i = 0; i < sz; i++) {
    int u = g[v][i];
    if (u == pr) {
      continue;
    }
    res += dfs(u, v);
  }
  cnt[res]++;
  cnt[n - res]++;
  return res;
}

int ans[N];

int main() {
  fact[0] = 1;
  invfact[0] = 1;
  for (int i = 1; i < N; i++) {
    fact[i] = (long long)fact[i - 1] * i % md;
    int x = 1, step = 1 << 30;
    while (step > 0) {
      x = (long long)x * x % md;
      if (step & (md - 2)) x = (long long)x * i % md;
      step >>= 1;
    }
    invfact[i] = (long long)invfact[i - 1] * x % md;
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    g[i].clear();
  }
  for (int i = 0; i < n - 1; i++) {
    int foo, bar;
    scanf("%d %d", &foo, &bar);
    foo--; bar--;
    g[foo].push_back(bar);
    g[bar].push_back(foo);
  }
  for (int i = 0; i < N; i++) {
    cnt[i] = 0;
  }
  dfs(0, -1);
  for (int i = 0; i < N; i++) {
    cnt[i] = (long long) cnt[i] * fact[i] % md;
  }
  vector <int> x, y;
  for (int i = 0; i < N; i++) {
    x.push_back(cnt[i]);
  }
  for (int i = N - 1; i >= 0; i--) {
    y.push_back(invfact[i]);
  }
  vector <int> z = multiply(x, y);
  for (int i = 1; i <= n; i++) {
    ans[i] = z[i + N - 1];
    ans[i] = (long long) ans[i] * invfact[i] % md;
    ans[i] = ((C(n, i) * 1LL * (n + 1) - ans[i]) % md + md) % md;
    printf("%d\n", ans[i]);
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:130:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:136:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &foo, &bar);
                               ^

Judge Result