题解 | #Pre-Post#

#include <iostream>
#include <cstring>
#include<map>
#include <algorithm>
using namespace std;
map<pair<int, int>, long long> aa;
long long pailie(int n, int m) {
    if (m == 1) return n;
    if (m == 0 || m == n) return 1;
    if (aa[make_pair(n, m)] == 0 && aa[make_pair(n, n - m)] == 0) {
        aa[make_pair(n, m)] = pailie(n - 1, m - 1) + pailie(n - 1, m)
            ; aa[make_pair(n, n - m)] = aa[make_pair(n, m)];
    }
    return  aa[make_pair(n, m)] == 0 ? aa[make_pair(n, n - m)] : aa[make_pair(n, m)];
}
long long dfs(int x, string s1, string s2) {

    if (s1.size() == 1) return x;
    int a = 0, b = 0; long long sum = 1; int cnt = 0;
    while (a < s1.size()) {
        for (int i = b; i < s2.size(); i++) {
            if (s1[a] == s2[i]) {
                cnt++; int len = i - b;
                if (len == 0) {
                    a = a + 1 + len;
                    b = i + 1; break;
                }
                else
                {
                    sum *= dfs(x, s1.substr(a + 1, len), s2.substr(b, len));

                    a = a + 1 + len;
                    b = i + 1; break;
                }
            }


        }
    }
   
    return pailie(x, cnt) * sum;

}
int main()
{
    int x; string s1, s2;
   
    while (cin >> x >> s1 >> s2) {
        if (s1.size() == 1) cout << 1 << endl;
        else
        cout << dfs(x, s1.substr(1,s1.size()-1), s2.substr(0,s2.size()-1)) << endl;
    }
    return 0;
}