Poj Solution 2775

http://poj.org/problem?id=2775

#include "stdio.h"


struct tree{
    int l, r;
    int v;
    int ans;
    int nds;
}t[200];
int n, m;

int new_node( int value ) {
    t[m].l = t[m].r = -1;
    t[m].v = value;
    t[m].nds = 1;
    m++;
    return m-1;
}

int a[200];

void insert( int value, int i ) {
    t[i].nds++;
    if( value <= t[i].v ) {
        if( t[i].l < 0 )
            t[i].l = new_node( value );
        else
            insert( value, t[i].l );
    }
    else {
        if( t[i].r < 0 )
            t[i].r = new_node( value );
        else
            insert( value, t[i].r );
    }
}

void creat() {
    int i;
    m = 0;
    new_node( a[0] );
    for( i=1; i<n; i++ )
        insert( a[i], 0 );
}

int gcd( int a, int b ) {
    int c;
    while( b ) {
        c = b;
        b = a%b;
        a = c;
    }
    return a;
}

int jc( int c, int a, int b ) {
    int i, j, k, t;
    int s[201], ans;

    for( i=c; i>a; i-- )
        s[c-i] = i;

    for( i=2; i<=b; i++ ) {
        k = i;
        for( j=0; k>1; j++ )
            if( ( t = gcd( k, s[j] ) ) > 1 )
                k/=t, s[j]/=t;
    }

    ans = 1;
    for( j=0; j<c-a; j++ )
        ans = ans*s[j]%9901;

    return ans;
}

void clac( int i ) {
    if( i < 0 )
        return;

    clac( t[i].l );
    clac( t[i].r );


    if( t[i].l < 0 ) {
        if( t[i].r < 0 )
            t[i].ans = 1;
        else
            t[i].ans = t[ t[i].r ].ans;
    }
    else if( t[i].r < 0 )
        t[i].ans = t[ t[i].l ].ans;
    else
        t[i].ans = t[ t[i].l ].ans * t[ t[i].r ].ans % 9901
        * jc( t[i].nds-1, t[t[i].l].nds, t[t[i].r].nds ) % 9901;
}

int main( ) {
    int i;
    while( scanf( "%d", &n ) == 1 ) {
        if( n <=0 )break;

        for( i=0; i<n; i++ )
            scanf( "%d", a+i );
        creat();
        clac( 0 );
        printf( "%dn", t[0].ans );
    }
    return 0;
}