AtCoder Grand Contest 005

Submission #1355041

Source codeソースコード

#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

Task問題 F - Many Easy Problems
User nameユーザ名 EmanuelNrx
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1900
Source lengthソースコード長 3051 Byte
File nameファイル名
Exec time実行時間 438 ms
Memory usageメモリ使用量 44288 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0,example1,example2
All 1900 / 1900 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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