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 |
|
|
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 |