Submission #2212471


Source Code Expand

#include <bits/stdc++.h>

using std::pair;
using std::vector;
using std::string;

typedef long long ll;
typedef pair<int, int> pii;

#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)

template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

const int oo = 0x3f3f3f3f;

string procStatus() {
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}

template <typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x *= f;
}

const int g = 5;
const int N = 1 << 20;
const int mo = 924844033;

int fpm(int x, int y) {
    int res = 1;
    for(; y > 0; y >>= 1) {
        if(y & 1)
            res = (ll) res * x % mo;
        x = (ll) x * x % mo;
    }
    return res;
}

namespace Poly {
    int n;

    void init(int _n) {
        n = _n;
        while(n > (n & -n)) n += (n & -n);
    }

    void dft(int *x, int ty) {
        for(int i = 0, j = 0; i < n; ++i) {
            if(i < j) std::swap(x[i], x[j]);
            for(int l = n >> 1; (j ^= l) < l; l >>= 1);
        }

        for(int l = 1; l < n; l <<= 1) {
            int wn = fpm(g, (mo - 1) / l / 2);
            if(ty == -1) wn = fpm(wn, mo - 2);

            for(int i = 0; i < n; i += l << 1) {
                int w = 1;
                for(int j = 0; j < l; ++j) {
                    int u = x[i + j];
                    int v = (ll) x[i + j + l] * w % mo;

                    x[i + j] = (u + v) % mo;
                    x[i + j + l] = (u - v + mo) % mo;
                    w = (ll) w * wn % mo;
                }
            }
        }

        if(ty == -1) {
            int inv = fpm(n, mo - 2);
            for(int i = 0; i < n; ++i) {
                x[i] = (ll) x[i] * inv % mo;
            }
        }
    }
}

int n, k;
vector<int> G[N + 5];
int x[N + 5], y[N + 5], sz[N + 5];

void dfs(int u, int f = 0) {
    ++ x[n];
    sz[u] = 1;
    for(const auto& v : G[u]) if(v ^ f) {
        dfs(v, u);
        sz[u] += sz[v];
        -- x[sz[v]], -- x[n - sz[v]];
    }
}

int main() {
#ifdef Wearry
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    read(n);
    for(int i = 1; i < n; ++i) {
        static int u, v;
        read(u), read(v);
        G[u].pb(v), G[v].pb(u);
    }

    dfs(1);

    int fac = 1;
    for(int i = 1; i <= n; ++i) {
        fac = (ll) fac * i % mo;
        x[i] = (ll) x[i] * fac % mo;
    }

    fac = 1;
    for(int i = n; i >= 0; --i) {
        y[i] = fpm(fac, mo - 2);
        fac = (ll) fac * (n - i + 1) % mo;
    }

    Poly::init(2*n+1);
    Poly::dft(x, 1), Poly::dft(y, 1);
    for(int i = 0; i < Poly::n; ++i) x[i] = (ll) x[i] * y[i] % mo;
    Poly::dft(x, -1);

    fac = 1;
    for(int i = n+1; i <= 2*n; ++i) {
        fac = (ll) fac * (i - n) % mo;
        printf("%lld\n", (ll) x[i] * fpm(fac, mo - 2) % mo);
    }

    return 0;
}

Submission Info

Submission Time
Task F - Many Easy Problems
User Wearry
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3348 Byte
Status WA
Exec Time 296 ms
Memory 49920 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1900
Status
AC × 3
AC × 36
WA × 12
Set Name Test Cases
Sample example0, example1, example2
All doublestar0, doublestar1, doublestar2, doublestar3, doublestar4, example0, example1, example2, line0, line1, line2, line3, line4, maxrand0, maxrand1, maxrand10, maxrand11, maxrand12, maxrand13, maxrand14, maxrand15, maxrand16, maxrand17, maxrand18, maxrand19, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, rand0, rand1, rand2, rand3, rand4, rand5, rand6, rand7, rand8, rand9, star0, star1, star2, star3, star4
Case Name Status Exec Time Memory
doublestar0 AC 256 ms 38260 KB
doublestar1 AC 263 ms 42360 KB
doublestar2 AC 255 ms 42360 KB
doublestar3 AC 252 ms 42360 KB
doublestar4 AC 253 ms 42360 KB
example0 AC 10 ms 28928 KB
example1 AC 9 ms 28928 KB
example2 AC 10 ms 28928 KB
line0 WA 268 ms 49920 KB
line1 AC 269 ms 49920 KB
line2 WA 270 ms 49920 KB
line3 AC 269 ms 49920 KB
line4 AC 269 ms 49920 KB
maxrand0 AC 296 ms 42240 KB
maxrand1 AC 291 ms 42240 KB
maxrand10 WA 286 ms 42240 KB
maxrand11 AC 285 ms 42240 KB
maxrand12 AC 287 ms 42240 KB
maxrand13 AC 287 ms 42240 KB
maxrand14 AC 287 ms 42240 KB
maxrand15 WA 294 ms 42240 KB
maxrand16 AC 284 ms 42240 KB
maxrand17 WA 285 ms 42240 KB
maxrand18 AC 288 ms 42240 KB
maxrand19 WA 285 ms 42240 KB
maxrand2 AC 289 ms 42240 KB
maxrand3 WA 285 ms 42240 KB
maxrand4 AC 292 ms 42240 KB
maxrand5 WA 289 ms 42240 KB
maxrand6 WA 287 ms 42240 KB
maxrand7 AC 286 ms 42240 KB
maxrand8 WA 285 ms 42240 KB
maxrand9 WA 289 ms 42240 KB
rand0 AC 13 ms 29056 KB
rand1 AC 10 ms 28928 KB
rand2 AC 12 ms 29056 KB
rand3 AC 13 ms 29056 KB
rand4 AC 11 ms 28928 KB
rand5 AC 13 ms 29056 KB
rand6 WA 12 ms 29056 KB
rand7 AC 13 ms 29056 KB
rand8 AC 10 ms 28928 KB
rand9 AC 11 ms 28928 KB
star0 AC 246 ms 42740 KB
star1 AC 246 ms 42740 KB
star2 AC 246 ms 42740 KB
star3 AC 246 ms 42740 KB
star4 AC 245 ms 42740 KB