Pre-Post

import java.util.*;
public class Main{
    private static long num=1;
    private static long numArr[];

    private static void initArr(){
        numArr=new long[21];
        numArr[0]=1;
        for(int i=1;i<21;i++){
            numArr[i]=numArr[i-1]*i;
        }
    }

    private static long CaculateCom(int subNum,int n){
        return numArr[n]/(numArr[n-subNum]*numArr[subNum]);
    }

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        initArr();
        while(scanner.hasNext()){
            int n=scanner.nextInt();
            String preOrder=scanner.next();
            String postOrder=scanner.next();
            num=1;
            CaculateTree(n,preOrder,postOrder);
            System.out.println(num);
        }
    }

    private static void CaculateTree(int n,String preOrder,String postOrder){
        int len=preOrder.length();
        if(len==1){
            return;
        }
        int count=0;
        preOrder=preOrder.substring(1);
        postOrder=postOrder.substring(0,len-1);
        while(!"".equals(preOrder)){
            int index=postOrder.indexOf(preOrder.charAt(0))+1;
            String newPre=preOrder.substring(0,index);
            String newPost=postOrder.substring(0,index);
            preOrder=preOrder.substring(index);
            postOrder=postOrder.substring(index);
            count++;
            CaculateTree(n,newPre,newPost);
        }
        num*=CaculateCom(count,n);
    }

}  

#include <string>
#include <tuple>
#include <list>
#include <cstdio>
// 求n的阶乘
long long factorial(int n){
    long long r = 1;
    for (int i = 1; i <= n; i++){
        r *= i;
    }
    return r;
}
// 求 n, m 的组合 C(n, m)
// 利用 C(n, m) == C(n, n - m) 的特点，计算容易的
long long combination(int n, int m){
    int max = m > (n - m) ? m : (n - m);
    long long numerator = 1;
    for (int i = max + 1; i <= n; i++){
        numerator *= i;
    }
    return numerator / factorial(n - max);
}// 重命名类型，类似于 typedef 作用
using PrePost = std::tuple<std::string, std::string>;
// 给出一棵树的前序+后序，利用最上面注释的原理 // 把每棵子树的前序+后序切分出来
std::list<PrePost> splitSubTrees(std::string const& pre, std::string const& post){
    std::list<PrePost> list{};
    size_t preIdx = 1;
    size_t lastPost = 0;
    while (preIdx < pre.size()){
        char rootValue = pre[preIdx];
        size_t postIdx = post.find(rootValue);
        int countOfNode = postIdx - lastPost + 1;
        list.emplace_back(std::make_tuple( pre.substr(preIdx, countOfNode), post.substr(lastPost, countOfNode) ) );
        preIdx += countOfNode;
        lastPost += countOfNode;
    }
    return list;
}
// 递归的求解每一层的可能性，直到树中只剩一个或者零个结点
long long calculateNumOfPossibilities(int m, std::string const& pre, std::string const& post){
    if (pre.size() == 0 || pre.size() == 1){
        return 1;
    }
    std::list<PrePost> subTrees = splitSubTrees(pre, post);
    long long result = combination(m, subTrees.size());
    for (PrePost const& prePost : subTrees){
        result *= calculateNumOfPossibilities(m,std::get<0>(prePost), std::get<1>(prePost));
    }
    return result;
}
int main(){
    int m;
    char pre[30];
    char post[30];
    while (scanf("%d %s %s", &m, pre, post) != EOF){
        printf("%lld\n", calculateNumOfPossibilities(m, pre, post));
    }
    return 0;
}

#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int ans, m;
char pre[27], post[27];
map<char, int> postidx;
//相应字母在post中的下标,因为每个节点都是唯一的，所以可以建立一个索引
void Count(int preS, int preE, int postS, int postE);
int mCk(int m, int k);

int main()
{
    while (scanf("%d %s %s", &m, pre, post) != EOF)
    {
        ans = 1;
        for (int i = 0; i<strlen(post); i++)
            postidx[post[i]] = i;
        Count(0, strlen(pre) - 1, 0, strlen(post) - 1);
        printf("%d\n", ans);
    }//while
    return 0;
}//main

void Count(int preS, int preE, int postS, int postE)//指示先序和后序某段区间
{
    if (preS >= preE)
        return;
    int i = preS + 1, cnt = 0;//cnt统计子树的个数,i是标识当前树的根节点的子树的根节点，在pre中的下标
    int idx = postidx[pre[i]];
    while (i <= preE)
    {
        Count(i, i + idx - postS, postS, idx);
        cnt++;
        if (idx != postE - 1)//子树不止一个,把要递归搜索的树的区间整体移动
        {
            i += idx - postS + 1;   //idx-postS是刚刚递归过的子树的大小
                                  //i要跨过这个区间，找到下一个要搜索的根节点
            postS = idx + 1;    //post的区间起始位置也要前进1位
            idx = postidx[pre[i]];//idx重新定位下一个要搜索的子树根节点在post中的下标
        }
        else
            break;//完成对当前区间中所有字数根节点的全部搜索
    }
    ans *= mCk(m, cnt);//计算排列组合，cnt表示当前层有几个子树
}

int mCk(int m, int k)
{
    int numerator = 1, denominator = 1;
    for (int i = 0; i<k; i++, m--)
        numerator *= m;
    for (int i = 1; i <= k; i++)
        denominator *= i;
    return numerator / denominator;
}

#include<iostream>
#include<string> 
using namespace std;  
int c[21][21],n;
long long solve(string pre,string post){  
    long long sum=1;  
    int num=0,k=0,i;  
    pre.erase(pre.begin());  
    post=post.substr(0, post.length()-1);  
    while (k<pre.length())
        for (i=0;i<post.length();i++)  
            if (pre[k]==post[i]){  
                sum*=solve(pre.substr(k,i-k+1),post.substr(k,i-k+1));  
                num++,k=i+1;break;  
            }  
    sum*=c[num][n];
    return sum;  
}  
void init(){  
    int i,j;  
    c[0][1]=c[1][1]=1;  
    for(i=2;i<21;i++)    
        for(c[0][i]=1,j=1;j<=i;j++) 
            if(i==j) c[j][i]=1;  
            else c[j][i]=c[j-1][i-1]+c[j][i-1];  
  
}  
int main(){  
    string pre,post;  
    init();  
    while(cin>>n>>pre>>post&&n)
        cout<<solve(pre,post)<<endl;
} 

#include <iostream>
#include <string>
using namespace std;
// pre: root,child1->childm
// post:child1->childm,root

void getPosssible(string pre, string post, int m, int& ans) {
    if(pre == "") return;
    if (pre.front() == post.back()) {
        // 位于同一颗根节点的树上
        int len = post.size();
        ans *= m;
        getPosssible(pre.substr(1,len-1), post.substr(0,len-1), m, ans);
    } else {
        // 位于不同根节点的树上
        int rootNum = 0;
        while (!pre.empty()) {
            char root1 = pre.front();
            int root1Len = post.find(root1) ;
            getPosssible(pre.substr(1, root1Len), post.substr(0, root1Len),  m,  ans);
            rootNum++;
            int restLen = post.size() - root1Len;
            if(!restLen) break;
            pre = pre.substr(root1Len+1, restLen);
            post = post.substr(root1Len+1, restLen);
        }
        // 得到分支数
        int a = 1, b = 1;
        for (int i = 0 ; i < rootNum; i++) {
            a *= (m - i);
            b *= (rootNum - i);
        }
        ans *= (a / b);

    }
}
int main() {
    int m;
    while (cin >> m && m != 0) {
        string pre, post;
        cin >> pre >> post;
        int ans = 1;
        int len = post.size();
        getPosssible(pre.substr(1,len-1), post.substr(0,len-1), m, ans);
        cout << ans << '\n';
    }
}
// 64 位输出请用 printf("%lld")

#include <iostream>
using namespace std;

//这里认为子树位置一样就算同一种，所以是用组合数而不是排列数
//注意组合数的求法：C(n,k)=C(n-1,k)+C(n-1,k-1)

const int M = 25;
int C[M][M];
int m;
string preTr, postTr;

int diffTree(string pre, string post)
{
    if(pre.size() == 1 && post.size()==1)
        return 1;
    
    int res = 1;
    pre.erase(0, 1);
    post.pop_back();

    int i=0, j=0;
    int subtree = 0;
    while(i<pre.size())
    {
        int k = post.find(pre[i], j);
        int trees = diffTree(pre.substr(i, k-j+1), post.substr(j, k-j+1));
        subtree++;
        res*=trees;
        i+=(k-j+1);
        j=k+1;
    }

    return res*C[m][subtree];
}

int main() 
{
    C[0][0]=1;
    for(int i=1;i<M;i++)
    {
        C[i][0]=1;
        for(int j=1;j<i;j++)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
        C[i][i]=1;
    }
    while(cin>>m>>preTr>>postTr)
        cout<<diffTree(preTr, postTr)<<endl;

    return 0;
}
// 64 位输出请用 printf("%lld")

#include<iostream>
#include<string>
#include<vector>
using namespace std;


/*
输入描述：
输入将包含多个问题实例。每个实例将由一行m s1 s2组成，表示树是m元树，s1是前序遍历，s2是后序遍历。所有遍历字符串将由小写字母字符组成。
对于所有输入实例，1<=m<=20，s1和s2的长度将介于1和26之间（包括1和26）。如果s1的长度是k（当然，这与s2的长度相同），则字母表的前k个字母将用于字符串。
输入行0将终止输入。
*/

/*
输出描述：
对于每个问题实例，您应该输出一行，其中包含可能的树的数量，这将导致实例的预排序和后排序遍历。所有输出值都将在32位有符号整数的范围内。
对于每个问题实例，保证至少有一个树具有给定的预排序和后排序遍历。
*/


//保存子树的前序和后序遍历结果
struct SubTree{
    
    SubTree(const string& pre,const string& post)
        :_pre(pre)
        ,_post(post)
    {}
    
    string _pre;
    string _post;
};


//求n的阶乘
long long Fac(int n)
{
    long long f = 1;
    for(int i = 1; i <= n; i++)
    {
        f *= i;
    }
    return f;
}

//求C(n,m) = C(n,n-m)
long long CalcCom(int n,int m)
{
    m = m < (n-m)?m:(n-m);
    long long r = 1;
    for(int i = n; i >= n-m+1; i--)
    {
        r *= i;
    }
    return r / Fac(m);
}


vector<SubTree> CalcSubTree(const string& pre,const string& post)
{
    size_t subRootPreIdx = 1;
    size_t postFirst = 0;  //子树在后序遍历结果中第一个元素的位置
    
    vector<SubTree> v;
    while(subRootPreIdx < pre.size())
    {
        //确定子树的根结点
        char subRoot = pre[subRootPreIdx];
        
        //确定根在后序遍历结果中的位置
        char subRootPostIdx = post.find(subRoot);
        
        //计算该子树中结点的个数
        size_t subTreeNodeCount = subRootPostIdx - postFirst + 1;
        
        //找到该棵子树钱些许遍历结果 - 找到该棵子树后序遍历结果 - 构造子树
        SubTree subTree(pre.substr(subRootPreIdx,subTreeNodeCount),post.substr(postFirst,subTreeNodeCount))
;
        v.push_back(subTree);
        
        //根据下一棵子树根在前序遍历结果中的下标
        subRootPreIdx += subTreeNodeCount;
        
        //更新下一棵子树中第一个结点在后序遍历中的下标
        postFirst += subTreeNodeCount;
    }
    return v;
}

long long CalcTreePossible(int m,const string& pre,const string& post)
{
    //如果树中只有一个结点 -- 树的可能性是唯一的
    if(1 == pre.size()){
        return 1;
    }
    
    //先找出每一层根结点的所有子树
    vector<SubTree> v = CalcSubTree(pre,post);
    
    //计算根结点子树的可能性 --- 组合
    long long result = CalcCom(m,v.size());
    
    for(auto& e: v){
        result *= CalcTreePossible(m,e._pre,e._post);  //递归
    }
    return result;
}

int main()
{
    int m;  //多少叉树
    string pre,post;
    while(cin >> m >> pre >> post)
    {
        if(m == 0){
            break;
        }
        cout << CalcTreePossible(m,pre,post) << endl;
    }
    return 0;
}

import java.util.*;
class SubTree{
    public SubTree(String pre,String post){
        this.pre = pre;
        this.post = post;
    }
    String pre;
    String post;
}
public class Main{
    //计算阶乘
    public static  long fac(int n){
        long f = 1;
        for(int i = 1;i <= n;i++){
            f *= i;
        }
        return f;
    }
    //计算C n m 
    public static long calcCom(int n,int m){
         m = m < (n - m)? m : (n - m);
        long r = 1;
        for(int i = n;i >= n - m + 1;i--){
            r *= i;
        }
        return r / fac(m);
    }
    public static List<SubTree> calcSubTree(String prev,String post){
       //子树的根在前序遍历结果中的位置
        int subRootPreIdx = 1;
        //后序遍历
        int postFirst = 0;
         List<SubTree> subTreeList = new ArrayList<>();
        while(subRootPreIdx < prev.length()){
            //确认该棵子树的根节点
            char rootSub = prev.charAt(subRootPreIdx);
            int subRootPostIdx = post.indexOf(rootSub);
            int subTreeNodeCount = subRootPostIdx - postFirst + 1;
            //从前序和后续遍历结果中分离出该棵子树的前序和后序遍历结果
            SubTree subTree = new SubTree(
                  prev.substring(subRootPreIdx,subRootPreIdx + subTreeNodeCount),
                  post.substring(postFirst,postFirst + subTreeNodeCount)
            );
            subTreeList.add(subTree);
            //继续分离下一棵子树
            subRootPreIdx += subTreeNodeCount;
            postFirst += subTreeNodeCount;
        }
        return subTreeList;
    }
    public static long CalcTreePossible(int m,String pre,String post){
        if(pre.isEmpty() || pre.length() == 1){
            return 1;
        }
        //先分离出根节点有多少棵树
       List<SubTree> subTree =  calcSubTree(pre,post);
        //根节点子树可能性的组合结果
        long result = calcCom(m,subTree.size());
        //根的子树有多少种可能性
        for(SubTree e : subTree){
            result *= CalcTreePossible(m,e.pre,e.post);
        }
        return result;
    }
    public static void main(String[] args){
         Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int m = in.nextInt();
            if(m == 0){
                break;
            }
            //接收子树的前序和后续遍历结果
            String pre = in.next();
            String post = in.next();
            
            System.out.println(CalcTreePossible(m,pre,post));
        }
    }
}

#include"iostream"
using namespace std;
/*计算组合数c(m, n)*/
int f(int k, int m, int n){
    if(k== n+ 1|| m== 0|| m> (n- k+ 1)){
        if(m== 0){return 1;}
        else{return 0;}
    }else{
        return f(k+ 1, m, n)+ f(k+ 1, m-1, n);
    }
}
/*以该先序和后序能形成的n叉树的个数*/
int g(string nlr, string lrn, int n){
    if(nlr.length()== 1){return 1;}// 结束条件
    else{
        int fe= 0, sum= 1, m= 0;
        while(fe< nlr.length()-1){// 考虑固定一种子树的顺序 则n叉树的个数等于各个子树所能形成n叉树个数的连乘积
            int len= lrn.find(nlr[fe+ 1])+ 1;
            string s1= nlr.substr(fe+ 1, len);
            string s2= lrn.substr(0, len);
            sum*= g(s1, s2, n);m++;fe+= len;
            lrn= lrn.substr(len);
        }
        return f(1, m, n)* sum;// 考虑全部的顺序
    }
}
int main(){
    string s1, s2;int n;
    while(cin>> n>> s1>> s2){
        cout<< g(s1, s2, n)<< endl;
    }
}

#include <iostream>
#include <string>

const int N = 1000;
int n;
using namespace std;

int c[N][N]; //c[i][j] 表示从i个数里面选j个

int solve(string pre,string post)
{
    if(pre.size() == 1 && pre[0] == post[0]) return 1;
    pre.erase(pre.begin());
    post.erase(post.end() - 1);

    int sum = 1;
    int k = 0;
    int cnt = 0 ;//记录本层中有几棵树
    for(int i = 0; i < post.size(); i ++ )
    {
        if(post[i] == pre[k])
        {
            sum *= solve(pre.substr(k,i - k + 1),
                        post.substr(k,i - k + 1));
            k = i + 1;
            cnt ++;
        }
    }
    sum *= c[n][cnt];
    return sum;
}

int main()
{
    c[0][0] = 1;
    for(int i = 1; i < N; i ++)
        for(int j = 0; j <= i; j ++)
        {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    string pre,post;
    while(cin >> n >> pre >> post)
    {
        cout << solve(pre,post) << endl;
    }
    return 0;
}

#include<iostream>
#include<string>
using namespace std;

long long N[21],num;
int n;
void ComputeN()
{
    N[0] = 1;
    for(int i = 1;i < 21;i++)
    {
        N[i] = N[i - 1] * i;
    }
}

int CMN(int m,int n)
{
    return N[n] / (N[m] * N[n - m]); 
}

void DFS(string pre,string post)
{
    if(pre.size() == 1) return;
    int count = 0;
    pre = pre.substr(1);
    post = post.substr(0,post.size() - 1);
    while(pre != "")
    {
        int index = post.find(pre[0]) + 1;
        string newpre = pre.substr(0,index);
        string newpost = post.substr(0,index);
        pre = pre.substr(index);
        post = post.substr(index);
        count++;
        DFS(newpre,newpost);
    }
    num *= CMN(count,n);
}

int main()
{
    string s1,s2;
    ComputeN();
    while(cin >> n >> s1 >> s2)
    {
        num = 1;
        DFS(s1,s2);
        cout << num << endl;
    }
    return 0;
}

//m叉树根节点孩子结点个数为n,可以得到组合数C(m,n)，递归调用根节点的各个孩子节点为根
//的子树,得到n个组合数.这n个组合数与组合数C(m,n)的和即为以先序与后序序***定的树的
//总个数
//其中每个阶段计算组合数采用分而治之的思想，类比二叉树先序后序递归调用得中序的方式
//可以将先序和后序分为n个子树对应的先序后序子序列，统计子序列的个数即为可得到n，
#include<cstdio>
(802)#include<cstring>
#include<map>
using namespace std;
char pre[30],post[30];
int m;
map<char,int> mp;
int ccal(int n1,int m1){
    int sum=1;
    for(int i=1;i<=m1;++i){
        sum=sum*(n1-m1+i)/i;
    }
    return sum;
}
int cal(int pl,int pr,int pol,int ***bsp;   if(pl>=pr){
        return 1;
    }
    int ans=1,i=pl+1,l=pol,r=mp[pre[pl+1]];
    int sum=0;
    while(i<=pr){
        ans*=cal(i,i+r-l,l,r);
        sum++;
        i=i+r-l+1;
        l=r+1;
        if(i<=pr)
           r=mp[pre[i]];
    }
    ans*=ccal(m,sum);
    return ans;
}
int main(){
    while(scanf("%d %s %s",&m,pre,post)!=EOF){
           int len=strlen(pre);
           mp.clear();
           for(int i=0;i<strlen(post);++i){
                mp[post[i]]=i;
           }
           int cnt=cal(0,len-1,0,len-1);
           printf("%d\n",cnt);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int com(int n,int m)
{
    int up=1,down=1;
    for(int i=1;i<=n;up*=(m-i+1),down*=i++);
    return up/down;
}
int dfs(string pre,string post,int m)
{
    if(pre.length()==1)return 1;
    vector<string> preSplit,postSplit;
    int preCut=1,postCut1=0,postCut2;
    while(preCut!=pre.length())
    {
        postCut2=post.find(pre[preCut]);
        preSplit.push_back(pre.substr(preCut,postCut2-postCut1+1));
        postSplit.push_back(post.substr(postCut1,postCut2-postCut1+1));
        preCut+=postCut2-postCut1+1;
        postCut1=postCut2+1;
    }
    int n=preSplit.size(),sum=1;
    for(int i=0;i<n;++i)sum*=dfs(preSplit[i],postSplit[i],m);
    return sum*com(n,m);
}
int main()
{
    int  m;
    string pre,post;
    cin>>m>>pre>>post;
    cout<<dfs(pre,post,m);
    return 0;
}