Submission #907342

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int const MOD = 924844033;
int mul(int x, int y) {
  return (int) ((long long) x * y % MOD);
}

int modpow(int a, int b) {
  int ret = 1;
  while (b > 0) {
    if (b & 1) {
      ret = mul(ret, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return ret;
}
void add(int &a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
}

int const N = 1234567;
int FACT[N], INVFACT[N], INV[N];

int c(int n, int k) {
  if (k > n || k < 0) return 0;
  return mul(FACT[n], mul(INVFACT[k], INVFACT[n - k]));
}

int ans[N];
int n;

int sz[N];

vector<int> edges[N];

int f[N];


void dfs(int v, int pv) {
  sz[v] = 1;
  for (int to : edges[v]) {
    if (to != pv) {
      dfs(to, v);
      sz[v] += sz[to];
    }
  }
  add(f[n], 1);
  add(f[n - sz[v]], MOD - 1);
  for (int to : edges[v]) {
    if (to != pv) {
      add(f[sz[to]], MOD - 1);
    }
  }
}

int const G = 5;
int ROOT;
int const F = 21;
int rpws[(1 << F) + 1];

int inverse(int x, int bits) {
  int y = 0;
  for (int i = 0; i < bits; i++) {
    y = (y << 1) | (x & 1);
    x >>= 1;
  }
  return y;
}
int px[1 << F], py[1 << F];

void fft(int *a, int bits, bool inv) {
  int n = 1 << bits;
  for (int i = 0; i < n; i++) {
    int j = inverse(i, bits);
    if (i < j) {
      std::swap(a[i], a[j]);
    }
  }
  for (int len = 2; len <= n; len <<= 1) {
    int half = len >> 1;
    int step = (1 << F) / len;
    for (int i = 0; i < n; i += len) {
      int k = inv ? (1 << F) : 0;
      for (int j = 0; j < half; j++) {
        int u = a[i + j];
        int v = mul(a[i + j + half], rpws[k]);
        int x = u;
        add(x, v);
        int y = u;
        add(y, MOD - v);
        a[i + j] = x;
        a[i + j + half] = y;
        if (inv) {
          k -= step;
        } else {
          k += step;
        }
      }
    }
  }
  if (inv) {
    int invn = modpow(n, MOD - 2);
    for (int i = 0; i < n; i++) {
      a[i] = mul(a[i], invn);
    }
  }
}

void mul(int *px, int *py, int bits) {  
  fft(px, bits, false);
  fft(py, bits, false);
  int n = 1 << bits;
  for (int i = 0; i < n; i++) {
    px[i] = mul(px[i], py[i]);
  }
  fft(px, bits, true);
}

void go(int l, int r) {
  if (l + 1 >= r) return;
  int mid = (l + r) >> 1;
  go(l, mid);
  go(mid, r);
  int len = (r - l + 1) / 2 + 2;
  int p2 = 1;
  int bits = 0;
  while (p2 < len) {
    p2 <<= 1;
    ++bits;
  }
  fill(px, px + 2 * p2, 0);
  fill(py, py + 2 * p2, 0);
  for (int i = mid; i < r; i++) {
    px[i - mid] = f[i];
  }
  // for (int i = 0; i < p2; i++) printf("%d ", px[i]);
  // printf("* ");
  for (int i = l; i < mid; i++) {
    py[p2 - (i - l) - 1] = INVFACT[i];
  }
  // for (int i = 0; i < p2; i++) {
  //   printf("%d ", py[i]);
  // }
  int lsize = mid - l;
  mul(px, py, bits + 1);
  // printf(" =");
  // for (int i = 0; i < 2 * p2; i++) printf("%d ", px[i]);
  // puts("");
  for (int i = p2 - lsize; i < 2 * p2; i++) {
    add(ans[i - (p2 - lsize) + 1], px[i]);
  }
}

int main() {
  int po = (MOD - 1) / (1 << 21);
  ROOT = 1;
  for (int i = 0; i < po; i++) {
    ROOT = mul(ROOT, G);
  }
  rpws[0] = 1;
  for (int i = 1; i <= 1 << F; i++) {
    rpws[i] = mul(ROOT, rpws[i - 1]);
  }
  INV[1] = 1;
  for (int i = 2; i < N; i++) {
    INV[i] = mul(MOD - MOD / i, INV[MOD % i]);
  }
  FACT[0] = INVFACT[0] = 1;
  for (int i = 1; i < N; i++) {
    FACT[i] = mul(i, FACT[i - 1]);
    INVFACT[i] = mul(INV[i], INVFACT[i - 1]);
  }
  scanf("%d", &n);
  for (int i = 0; i + 1 < n; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    --v;
    --u;
    edges[v].push_back(u);
    edges[u].push_back(v);
  }
  dfs(0, -1);
  for (int i = 0; i <= n; i++) f[i] = mul(f[i], FACT[i]);
  go(0, n + 1);
  for (int i = 1; i <= n; i++) {
    printf("%d\n", mul(ans[i], INVFACT[i]));
  }
}

Submission Info

Compile Error

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

Judge Result