pku 2775 The Number of the Same BST

/*

The Number of the Same BST

求给定一个序列可以建成一个二叉排序树，问有多少种序列构成的树和这个一样

总结点个数n，每个节点为根的节点的个数size[i]

则结果为n!/(size[1]..size[n]).

*/

#include
#include
const int max=20025;

int tree[max],size[max];
int da[10001];
int an;

void insert(int x)
{
	int p,y;
	p=1;y=1;
	//查找
	while(size[p]!=0)
	{
		size[p]++;y=p;
		if(x<=tree[p])
			p=p*2;
		else p=p*2+1;
	}
    tree[p]=x;size[p]=1;
}

int inv(int x) //可以改进扩展欧几里德算法求
{
	int s,i;
	//ax=1 mod 9901;
    s=x;
	for(i=1;i<=9901;i++)
	{
       if(s%9901==1) return i;
	   s+=x;
	}
}

void lookup(int p)
{
	//printf("%d\n",size[p]);
	//求每个的逆 9901
	an=an*inv(size[p]);
	an%=9901;
	if(size[2*p+1]+size[2*p]==0)return;
	if(size[2*p]) lookup(2*p);
	if(size[2*p+1]) lookup(2*p+1);
}

int main()
{
	int i,n;
	while(scanf("%d",&n)&&n)
	{
		for(i=1;i<=n;i++)
		{scanf("%d",&da[i]);}

		memset(size,0,sizeof(size));
		memset(tree,0,sizeof(tree));
		
		tree[1]=da[1];size[1]=1;
	    for(i=2;i<=n;i++)
		insert(da[i]);
        //for(i=1;i<=10;i++)
			//printf("%d ",size[i]);
		//printf("\n");
		an=1;
		lookup(1);
		for(i=2;i<=n;i++)
			an=(an*i)%9901;
		printf("%d\n",an);
	}
}