BST

学习：http://www.cnblogs.com/zhuyf87/archive/2012/11/09/2763113.html

Binary Search Tree

题意：给一个1到n的排列，生成一棵BST，问有多少种排列生成的BST和这个相同。

要用到乘法原理

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=21;
 5 const int mod=9999991;
 6 
 7 int c[maxn][maxn];
 8 void init(){
 9     memset(c,0,sizeof(c));
10     for(int i=0;i<maxn;i++){
11         c[i][0]=1;
12         for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
13     }
14 }
15 struct BST{
16     int key;
17     int lc,rc;
18     int sz,lsz,rsz;
19 }bst[maxn];
20 void inser(int rt,int id,int x){
21     if(bst[rt].key==0){
22         bst[rt].key=x;
23         bst[rt].sz=1;
24         return ;
25     }
26     if(bst[rt].key>x){
27         if(!bst[rt].lc) bst[rt].lc=id;
28         inser(bst[rt].lc,id,x);
29     }else{
30         if(!bst[rt].rc) bst[rt].rc=id;
31         inser(bst[rt].rc,id,x);
32     }
33     bst[rt].lsz=bst[bst[rt].lc].sz;
34     bst[rt].rsz=bst[bst[rt].rc].sz;
35     bst[rt].sz= bst[rt].lsz+bst[rt].rsz+1;
36 
37 }
38 int main(){
39     int t;
40     scanf("%d",&t);
41     int n;
42     init();
43     while(t--){
44         scanf("%d",&n);
45         memset(bst,0,sizeof(bst));
46         int x;
47         for(int i=1;i<=n;i++){
48             scanf("%d",&x);
49             inser(1,i,x);
50         }
51         long long ans=1;
52         for(int i=1;i<=n;i++){
53             (ans*=c[bst[i].sz-1][bst[i].lsz])%=mod;
54         }
55         printf("%lld
",ans);
56     }
57 }

View Code

另一种写法，形式和后面代码比统一

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=21;
 5 const int mod=9999991;
 6 
 7 int c[maxn][maxn];
 8 void init(){
 9     memset(c,0,sizeof(c));
10     for(int i=0;i<maxn;i++){
11         c[i][0]=1;
12         for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
13     }
14 }
15 
16 struct Node{
17     Node* ch[2];
18     int v;
19     int s;
20 
21     Node(int v):v(v){ch[0]=ch[1]=NULL;s=1;}
22     int cmp(int x)const{
23         return x<v?0:1;
24     }
25 
26     void maintain(){
27         s=1;
28         if(ch[0]!=NULL) s+=ch[0]->s;
29         if(ch[1]!=NULL) s+=ch[1]->s;
30     }
31 };
32 Node* rt;
33 
34 int inser(Node* &o,int x){
35     if(o==NULL) o=new Node(x);
36     else {
37         int d=o->cmp(x);
38         inser(o->ch[d],x);
39         o->maintain();
40     }
41 }
42 ll ans;
43 void dfs(Node *o){
44     for(int i=0;i<2;i++) if(o->ch[i]!=NULL) dfs(o->ch[i]);
45     if(o->ch[0]!=NULL&&o->ch[1]!=NULL)
46         (ans*=c[(o->s)-1][o->ch[0]->s])%=mod;
47 }
48 int main(){
49     int t;
50     scanf("%d",&t);
51     int n;
52     init();
53     while(t--){
54         scanf("%d",&n);
55         int x;
56         rt=NULL;
57         for(int i=1;i<=n;i++){
58             scanf("%d",&x);
59             inser(rt,x);
60         }
61         ans=1;
62         if(rt!=NULL)dfs(rt);
63         else ans=0;
64         printf("%lld
",ans);
65     }
66 }

View Code