# 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;
}

This entry was posted in poj. Bookmark the permalink.