说明

本题要求计算给定先序遍历和后序遍历的m叉树的数量。关键在于理解树的遍历顺序如何反映树的结构，并利用组合数学计算可能的树形结构数量。

算法标签

• 深度优先搜索（DFS）：递归遍历树的结构
• 组合数学：计算子树排列的可能数量
• 树遍历：理解先序和后序遍历的性质

解题思路

1. 问题分析：

   • 给定m叉树的先序遍历s1和后序遍历s2，要求计算可能的树的数量。
   • 树的每个节点可以有最多m个子节点，顺序不同会导致不同的树。

2. 关键观察：

   • 先序遍历的第一个节点是根节点，后序遍历的最后一个节点也是根节点。
   • 根节点的子节点在先序和后序中的顺序可以帮助确定子树的范围。

3. 算法选择：

   • 使用DFS递归处理每个节点的子节点。
   • 对于每个节点，确定其子节点的可能排列组合数。
   • 利用组合数学计算子树的可能结构数量。

分析

1. 输入处理：

   • 读取m、s1和s2。
   • 初始化访问数组vis，标记已处理的节点。

2. DFS递归：

   • 从根节点开始，递归处理每个子节点。
   • 标记已访问的节点，避免重复处理。
   • 对于每个子节点，确定其在先序和后序中的位置关系。

3. 组合计算：

   • 对于每个节点的子节点，计算可能的排列组合数。
   • 使用组合公式计算从m个子节点中选择特定数量的方式。

4. 结果累积：

   • 将每个节点的组合数相乘，得到总的树的数量。

实现步骤

1. 输入读取：

   • 使用cin读取m、s1和s2。
   • 处理输入结束条件（m=0）。

2. 初始化：

   • 重置访问数组vis和结果ans。

3. DFS遍历：

   • 从根节点开始，递归处理子节点。
   • 标记已访问的节点，确保每个节点只处理一次。

4. 组合数计算：

   • 使用组合公式计算子节点的可能排列数。
   • 更新总的结果ans。

5. 输出结果：

   • 打印每个测试用例的树的数量。

代码解释

• 组合数计算：myc函数计算组合数C(n, r)，用于确定子节点的排列方式。
• DFS递归：dfs函数递归处理每个节点，确定子节点的可能结构。
• 主函数：处理输入，调用DFS，输出结果。

该方法通过DFS和组合数学高效地计算了可能的树形结构数量，确保在合理时间内解决问题。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
typedef long long ll;
 
int m;
string s1,s2;
bool vis[30];
 
int myc(int n,int r)
{
    ll sum=1;
    for(int i=1;i<=r;++i)
    {
        sum=sum*(n+1-i)/i;
    }
    return (int)sum;
}
 
int ans;
 
void dfs(int pre)
{
	
	if(vis[s1[pre]-'a'])return;
	vis[s1[pre]-'a']=1;
    for(int i=0;i<s2.size();++i)
    {
        if(s2[i]==s1[pre])
        {
        	
        	
            int son=0;
            for(int j=pre+1;j<s1.size();++j)
            {
                if(!vis[s1[j]-'a'])
                {
                	int k;
                	for(k=0;k<s2.size();++k)
                	{
						if(s1[j]==s2[k])break;
					}
					if(k<=i)
					{
						dfs(j);
                  	  	son++;
					}
                }
            }
            if(son){
                ans=ans*myc(m,son);
            }
            break;
        }
    }
    return;
}
 
int main()
{
//	freopen("data.txt","r",stdin);
    while(cin>>m)
    {
    	if(m==0)break;
    	cin>>s1>>s2;
        memset(vis,false,sizeof(vis));
        ans=1;
        dfs(0);
        printf("%d\n",ans);
    }
	return 0;
}