Submission #907079


Source Code Expand

#include <cstdio>
#include <cassert>
#include <vector>
using namespace std;

const int N = 200500;

vector<int> E[N];

const int MOD = 924844033;
int powmod(int x, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = 1ll * res * x % MOD;
        b >>= 1;
        x = 1ll * x * x % MOD;
    }
    return res;
}

int inv[N];
typedef long long llong;
int S[N];
int n;
int F[N], iF[N];
int A[N];

void DFS(int x, int p = -1) {
    S[x] = 1;
    for (int y : E[x]) {
        if (y != p) {
            DFS(y, x);
            S[x] += S[y];
        }
    }
    if (p != -1) {
        A[n - S[x]]++;
        A[S[x]]++;
    }
}

const int LEN = (1 << 19);
const int AL = 10179;

inline int calc(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b % 2 != 0) {
            res = (1LL * res * a) % MOD;
        }
        a = (1LL * a * a) % MOD;
        b /= 2;
    }
    return res;
}

const int AL1 = calc(AL, MOD - 2);

int c[LEN], a[LEN], b[LEN];

inline void fft(int* a, int n, bool fl) {
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n / 2;
        for (; j >= bit; bit /= 2) {
            j -= bit;
        }
        j += bit;
        if (i < j) {
            swap(a[i], a[j]);
        }
    }
    for (int len = 2; len <= n; len *= 2) {
        int wlen = (fl ? AL1 : AL);
        for (int i = len; i < LEN; i *= 2) {
            wlen = (1LL * wlen * wlen) % MOD;
        }
        for (int i = 0; i < n; i += len) {
            int w = 1;
            for (int j = 0; j < len / 2; ++j) {
                int u = a[i + j], v = (1LL * a[i + j + len / 2] * w) % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                w = (1LL * w * wlen) % MOD;
            }
        }
    }
    if (fl) {
        int inv = calc(n, MOD - 2);
        for (int i = 0; i < n; ++i) {
            a[i] = (1LL * a[i] * inv) % MOD;
        }
    }
}

int ans[N];

int cnk(int n, int k) {
    int ans = 1ll * F[n] * iF[n - k] % MOD;
    ans = 1ll * ans * iF[k] % MOD;
    return ans;

}

int main() {
    /*for (int al = 3; ; ++al) {
        if (calc(al, LEN) == 1 && calc(al, LEN / 2) != 1) {
            printf("al = %d\n", al);
            return 0;
        }
    }
    return 0;*/
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    F[0] = iF[0] = 1;
    for (int i = 1; i <= n; i++) {
        inv[i] = powmod(i, MOD - 2);
        F[i] = F[i - 1] * 1ll * i % MOD;
        iF[i] = iF[i - 1] * 1ll * inv[i] % MOD;
    }

    DFS(0);
    for (int i = 0; i <= n; i++) {
        a[n - i] = 1ll * A[i] * F[i] % MOD;
        b[i] = iF[i];
    }
    int len = 1;
    while (len < (2 * n))
        len <<= 1;
    fft(a, len, false);
    fft(b, len, false);
    for (int i = 0; i < len; i++)
        c[i] = 1ll * a[i] * b[i] % MOD;
    fft(c, len, true);
//    printf("%d\n", n);
    for (int k = 1; k <= n; k++) {
        ans[k] = 1ll * c[n - k] * iF[k] % MOD;
        ans[k] = (1ll * n * cnk(n, k) % MOD - ans[k] + MOD) % MOD;
        printf("%d\n", ans[k]);
    }
}

Submission Info

Submission Time
Task F - Many Easy Problems
User Zlobober
Language C++14 (GCC 5.4.1)
Score 1900
Code Size 3342 Byte
Status AC
Exec Time 301 ms
Memory 34560 KB

Compile Error

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1900 / 1900
Status
AC × 3
AC × 48
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 250 ms 23544 KB
doublestar1 AC 250 ms 23544 KB
doublestar2 AC 251 ms 23544 KB
doublestar3 AC 250 ms 23544 KB
doublestar4 AC 251 ms 23544 KB
example0 AC 7 ms 4992 KB
example1 AC 7 ms 4992 KB
example2 AC 7 ms 4992 KB
line0 AC 276 ms 34560 KB
line1 AC 273 ms 34560 KB
line2 AC 275 ms 34560 KB
line3 AC 275 ms 34432 KB
line4 AC 273 ms 34560 KB
maxrand0 AC 281 ms 23552 KB
maxrand1 AC 286 ms 23552 KB
maxrand10 AC 283 ms 23552 KB
maxrand11 AC 282 ms 23552 KB
maxrand12 AC 282 ms 23552 KB
maxrand13 AC 281 ms 23552 KB
maxrand14 AC 292 ms 23552 KB
maxrand15 AC 283 ms 23552 KB
maxrand16 AC 281 ms 23552 KB
maxrand17 AC 283 ms 23552 KB
maxrand18 AC 296 ms 23680 KB
maxrand19 AC 301 ms 23552 KB
maxrand2 AC 285 ms 23552 KB
maxrand3 AC 296 ms 23552 KB
maxrand4 AC 295 ms 23552 KB
maxrand5 AC 292 ms 23552 KB
maxrand6 AC 281 ms 23552 KB
maxrand7 AC 295 ms 23552 KB
maxrand8 AC 283 ms 23552 KB
maxrand9 AC 283 ms 23552 KB
rand0 AC 11 ms 5248 KB
rand1 AC 7 ms 4992 KB
rand2 AC 9 ms 5120 KB
rand3 AC 10 ms 5248 KB
rand4 AC 8 ms 4992 KB
rand5 AC 11 ms 5248 KB
rand6 AC 9 ms 5120 KB
rand7 AC 10 ms 5248 KB
rand8 AC 8 ms 4992 KB
rand9 AC 9 ms 5120 KB
star0 AC 244 ms 23924 KB
star1 AC 244 ms 23924 KB
star2 AC 244 ms 23924 KB
star3 AC 244 ms 23924 KB
star4 AC 244 ms 23924 KB