poj/1240.cpp at master · aimfly/poj · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
using namespace std;

struct node_t{
	int value;
	int count;
	struct node_t *child[20];
};
int m;
char pre[26];
char post[26];

void create_tree(struct node_t *root,char *pre,char *post,int len)
{
	int i,j;
	char c;
	memset(root->child,0,sizeof(root->child));
	root->count=0;
	root->value=0;
	for(i=0,j=0;i<len;){
		c=pre[i];
		while(c!=post[j]){
			j++;
		}
		if(i!=j){
			root->child[root->count]=(struct node_t *)malloc(sizeof(struct node_t));
			create_tree(root->child[root->count],&pre[i+1],&post[i],j-i);
		}
		root->count++;
		j++;
		i=j;
	}
}

int cmn(int m,int n)
{
	int ans=1;
	int i;
	for(i=0;i<n;++i){
		ans*=m;
		m--;
	}
	for(;n>1;--n){
		ans/=n;
	}
	return ans;
}

void cal_value(struct node_t *root)
{
	int value=1;
	int i;
	for(i=0;i<root->count;++i){
		if(root->child[i]!=NULL){
			if(root->child[i]->value==0){
				cal_value(root->child[i]);
			}
		    value*=root->child[i]->value;
		    free(root->child[i]);
		}
	}
	value*=cmn(m,root->count);
	root->value=value;
}


int main()
{
	struct node_t root;
    cin>>m;
    while(m){
    	cin>>pre;
    	cin>>post;
    	create_tree(&root,&pre[1],&post[0],strlen(pre)-1);
    	cal_value(&root);
    	cout<<root.value<<endl;
    	cin>>m;
    }
	return 0;
}