PKU 2775 The Number of the Same BST
http://poj.org/problem?id=2775
二分探索木を作るような数字の入力が与えられる。
この入力と同じような二分探索木が作れる入力は何通りあるかを答えろというような問題。
あるノードの右と左のノードに入る数列の順番が決まれば、それらはお互いに影響しないので、右と左のノード内それぞれの順番を守ればあとは問題ない。
nodeの右、左ポインタの初期化を忘れてREを何回かもらいました。
そのせいで普段書かないデストラクタを書いたり、あまりらしくない感じになりました。
が、長い関数がないので、いつもより読みやすいようなきがしてます。
あとこれで750問目。今までの1/3だけでも、なんとか頑張りぬきたい。
int in[100]; int com[301][301]; typedef struct _node{ int val; int chs; _node* le; _node* ri; _node(int val){ this->val=val; chs=0; le=0; ri=0; } ~_node(){ if(ri!=NULL)delete ri; if(le!=NULL)delete le; } }node; void insert(node*&p,int val){ if(p==NULL){ p=new node(val); return; } p->chs++; if(p->val<val)insert(p->ri,val); else insert(p->le,val); } void dfs(int&ans,node*p){ int b=0,s=0; if(p->le){ s+=p->le->chs+1; dfs(ans,p->le); } if(p->ri){ b+=p->ri->chs+1; dfs(ans,p->ri); } ans=(ans*com[b+s][min(b,s)])%9901; } void solv(int n){ rep(i,n)cin>>in[i]; int ans=1; node* root=new node(0); rep(i,n){ insert(root,in[i]); } dfs(ans,root); cout<<ans<<endl; delete root; } main(){ com[0][0]=1; for(int i=1;i<=200;++i){ com[i][0]=1; for(int j=1;j<=i;++j)com[i][j]=(com[i-1][j]+com[i-1][j-1])%9901; } int n; while(cin>>n,n){ solv(n); } }