2775.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2775  User Id:fzk 
Memory:44K  Time:0MS
Language:G++  Result:Accepted

Source 

#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( "%d\n", t[0].ans );
	}
	return 0;
}