Submission #1355041


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int DIM = 524289;
const int MOD = 924844033;

vector<int> edg[DIM];

int fct[DIM], inv[DIM], szt[DIM];
int pol1[DIM], pol2[DIM], ans[DIM];

void dfs( int x, int f, int n ) {
    szt[x] = 1;
    
    for( int y : edg[x] ) {
        if( y == f )
            continue;
        
        dfs( y, x, n ); szt[x] += szt[y];
        pol1[szt[y]] --; pol1[n - szt[y]] --;
    }
    
    return;
}

int lgput( int x, int n ) {
    if( n == 0 )
        return 1;
    
    int y = lgput( x, n >> 1 );
    y = ( 1LL * y * y ) % MOD;
    
    if( n & 1 )
        y = ( 1LL * y * x ) % MOD;
    
    return y;
}

void dft( int pol[DIM], int sz, int sgn ) {
    int lg = 0;
    while( (1 << lg) < sz )
        lg ++;
    
    for( int i = 0; i < sz; i ++ ) {
        int x = 0;
        for( int j = 0; j < lg; j ++ )
            if( i & (1 << j) ) x |= (1 << (lg - j - 1));
        
        if( i < x )
            swap( pol[i], pol[x] );
    }
    
    for( int len = 2; len <= sz; len <<= 1 ) {
        int rot = lgput( 5, ( MOD - 1 + sgn * (MOD - 1) / len) % (MOD - 1) );
        
        for( int i = 0; i < sz; i += len ) {
            int stp = 1;
            
            for( int j = i; j < i + (len >> 1); j ++ ) {
                int x = pol[j], y = ( 1LL * stp * pol[j + (len >> 1)] ) % MOD;
                
                pol[j] = ( x + y ) % MOD;
                pol[j + (len >> 1)] = ( x - y + MOD ) % MOD;
                
                stp = ( 1LL * stp * rot ) % MOD;
            }
        }
    }
    
    if( sgn == -1 ) {
        int aux = lgput( sz, MOD - 2 );
        
        for( int i = 0; i < sz; i ++ )
            pol[i] = ( 1LL * pol[i] * aux ) % MOD;
    }
    
    return;
}

void ntt( int pol1[DIM], int pol2[DIM], int sz1, int sz2, int n ) {
    int sz = 1;
    while( sz < sz1 + sz2 - 1 )
        sz <<= 1;
    
    dft( pol1, sz, 1 );
    dft( pol2, sz, 1);
    
    for( int i = 0; i < sz; i ++ )
        pol1[i] = ( 1LL * pol1[i] * pol2[i] ) % MOD;
    dft( pol1, sz, -1 );
    
    return;
}

int main( void ) {
    
    int n;
    cin >> n;
    
    for( int i = 2; i <= n; i ++ ) {
        int x, y;
        cin >> x >> y;
        
        edg[x].push_back( y );
        edg[y].push_back( x );
    }
    
    dfs( 1, 0, n );
    
    fct[0] = inv[0] = 1; pol1[n] = n;
    for( int i = 1; i < DIM; i ++ )
        fct[i] = ( 1LL * fct[i - 1] * i ) % MOD;
    
    inv[DIM - 1] = lgput( fct[DIM - 1], MOD - 2 );
    for( int i = DIM - 2; i >= 1; i -- )
        inv[i] = ( 1LL * inv[i + 1] * (i + 1) ) % MOD;
    
    for( int i = 0; i <= n; i ++ ) {
        pol2[i] = inv[n - i];
        pol1[i] = ( pol1[i] + MOD ) % MOD;
        pol1[i] = ( 1LL * pol1[i] * fct[i] ) % MOD;
    }
    
    ntt( pol1, pol2, n + 1, n + 1, n );
    for( int i = 1; i <= n; i ++ )
        cout << ( 1LL * inv[i] * pol1[i + n] ) % MOD << "\n";
    
    return 0;
}

Submission Info

Submission Time
Task F - Many Easy Problems
User EmanuelNrx
Language C++14 (GCC 5.4.1)
Score 1900
Code Size 3051 Byte
Status AC
Exec Time 438 ms
Memory 44288 KB

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 373 ms 31352 KB
doublestar1 AC 376 ms 31352 KB
doublestar2 AC 375 ms 31352 KB
doublestar3 AC 377 ms 31352 KB
doublestar4 AC 376 ms 31352 KB
example0 AC 13 ms 22784 KB
example1 AC 13 ms 22784 KB
example2 AC 13 ms 22784 KB
line0 AC 408 ms 44160 KB
line1 AC 409 ms 44288 KB
line2 AC 411 ms 44160 KB
line3 AC 407 ms 44160 KB
line4 AC 408 ms 44160 KB
maxrand0 AC 427 ms 31232 KB
maxrand1 AC 430 ms 31232 KB
maxrand10 AC 426 ms 31232 KB
maxrand11 AC 429 ms 31232 KB
maxrand12 AC 428 ms 31232 KB
maxrand13 AC 425 ms 31232 KB
maxrand14 AC 431 ms 31232 KB
maxrand15 AC 424 ms 31232 KB
maxrand16 AC 430 ms 31232 KB
maxrand17 AC 429 ms 31232 KB
maxrand18 AC 419 ms 31232 KB
maxrand19 AC 434 ms 31232 KB
maxrand2 AC 438 ms 31232 KB
maxrand3 AC 426 ms 31232 KB
maxrand4 AC 425 ms 31232 KB
maxrand5 AC 424 ms 31232 KB
maxrand6 AC 423 ms 31232 KB
maxrand7 AC 424 ms 31232 KB
maxrand8 AC 425 ms 31232 KB
maxrand9 AC 428 ms 31232 KB
rand0 AC 18 ms 22912 KB
rand1 AC 13 ms 22784 KB
rand2 AC 16 ms 22912 KB
rand3 AC 18 ms 22912 KB
rand4 AC 14 ms 22784 KB
rand5 AC 17 ms 22912 KB
rand6 AC 16 ms 22912 KB
rand7 AC 17 ms 22912 KB
rand8 AC 13 ms 22784 KB
rand9 AC 15 ms 22784 KB
star0 AC 353 ms 31732 KB
star1 AC 353 ms 31732 KB
star2 AC 352 ms 31732 KB
star3 AC 353 ms 31732 KB
star4 AC 352 ms 31732 KB