2290457_wa.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 89 行

#include <stdio.h>
#include <stdlib.h>
#define Init (Tree *)malloc(sizeof(Tree))

typedef struct node
{
	int v;
	int no;
	struct node *l, *r;
}Tree;
Tree *T;

double c(double m,double n)
{
	double i,s;
	
	s = 1;
	if(n >= m-n)
		n = m - n;
	for (i = m; i >= m-n+1; i--)
		s *= i/(i - (m - n));
	return s;
}

long cal(Tree *t)
{
	long n1, n2, n3, a, b;

	n1 = n2 = 1;
	a = b = t->no-1;
	if(t->l)
		b = t->l->no,n1 = cal(t->l);
	if(t->r)
		n2 = cal(t->r);
	n3 = (long)c(a,b);
	
	return ((n2%9901)*(n3%9901)*(n1%9901))%9901;
}

void solve(int n)
{
	int i, v;
	Tree *p, *q;

	T = Init;
	T->l = T->r = NULL;
	scanf("%d",&v);
	T->v = v;T->no = 1;
	for(i = 1; i < n; i++)
	{
		scanf("%d",&v);
		p = T;q = Init;q->v = v;q->l = q->r = NULL;q->no = 1;
		while(p)
		{
			p->no++;
			if(v<=p->v)
			{
				if(p->l)
					p = p->l;
				else
				{
					p->l = q;
					break;
				}
			}
			else
			{
				if(p->r)
					p = p->r;
				else
				{
					p->r = q;
					break;
				}
			}
		}
	}
	printf("%ld\n",cal(T));
}

int main()
{
	int n;

	while(scanf("%d",&n)==1,n)
		solve(n);
	return 1;
}