# 14118: 【原4118】travel

### 题目描述

author: Ca. 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4118

## Sample Input

``````10 abc bca
``````

## Sample Output

``````45
``````

## FineArtz's solution

``````/* travel */
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

long long FACT[21] = {0};

long long comb(long long n, long long k){
return FACT[n] / FACT[k] / FACT[n - k];
}

int m;
char s1[25], s2[25];

long long travel(char *s1, long long len1, char *s2, long long len2){
long long ret = 1, p1 = 1, p2 = 0;
long long child = 0;
while (p1 < len1){
for (int i = 0; i < len2; ++i){
if (s2[i] == s1[p1]){
p2 = i;
break;
}
}
ret *= travel(s1 + p1, p2 - p1 + 2, s2 + p1 - 1, p2 - p1 + 2);
p1 = p2 + 2;
++child;
}
ret *= comb(m, child);
return ret;
}

int main(){
FACT[0] = 1;
for (int i = 1; i <= 20; ++i)
FACT[i] = FACT[i - 1] * i;

cin >> m >> s1 >> s2;
long long len1 = strlen(s1), len2 = strlen(s2);
cout << travel(s1, len1, s2, len2);
return 0;
}
``````

## q4x3's solution

``````/**
* dfs
* 一个个找子树
**/
#include <iostream>
#include <stdio.h>
#include <cstring>

using namespace std;

int m;
char s1[30], s2[30];
int C[30];

void init() {
C[0] = 1;
for(int i = 1;i <= m;++ i)
C[i] = C[i - 1] * (m - i + 1) / i;
}

int dfs(int pre, int pos, int len) {
int cnt = 0, sum = 1;
for(int i = pre + 1, j = pos;i < pre + len;) {
int tmp1 = i, tmp2 = j;
while(j < pre + len - 1 && s1[tmp1] != s2[j])
++ i, ++ j;
++ cnt;
sum *= dfs(tmp1, tmp2, j - tmp2 + 1);
++ i; ++ j;
}
sum *= C[cnt];
return sum;
}

int main() {
scanf("%d%s%s", &m, s1, s2);
if(s1[0] != s2[strlen(s2) - 1]) {
printf("0\n");
return 0;
}
init();
printf("%d\n", dfs(0, 0, strlen(s1)));
}
``````

## victrid's solution

``````#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
long long dp[30][30][30] = {};
char pre[30];
char pos[30];
int m;
long long C[30][30] = {};
long long c(int h, int l) {
if (C[h][l] != 0)
return C[h][l];
if (h == l || h == 0)
return 1;
else
C[h][l] = c(h, l - 1) + c(h - 1, l - 1);
return C[h][l];
}
//It's my fault
//! every digit can appear only once.
long long search(int prep, int posp, int length) {
int total     = 0;
long long ans = 1;
for (int i = prep + 1, j = posp; i < prep + length;) {
int subpre = i, subpos = j;
while (j < posp + length - 1 && pre[subpre] != pos[j])
++i, ++j;
++total;
ans *= search(subpre, subpos, j - subpos + 1);
++i, ++j;
}
ans *= c(total, m);
return ans;
}

int main() {
scanf("%d %s %s", &m, pre, pos);
cout << search(0, 0, strlen(pre));
return 0;
}
``````

## zqy2018's solution

``````#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, m;
ll dp[28][28][28] = {0}, C[28][28] = {0};
char pre[30], in[30];
ll dfs(int st1, int st2, int l){
int tot = 0;
ll res = 1;
for (int i = st1 + 1, j = st2; i < st1 + l; ){
int lsti = i, lstj = j;
while (j < st2 + l - 1 && pre[lsti] != in[j])
++i, ++j;
++tot;
res *= dfs(lsti, lstj, j - lstj + 1);
++i, ++j;
}
res *= C[m][tot];
return res;
}
void init(){
scanf("%s%s", pre, in);
n = strlen(pre);
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];
}
}
void solve(){
printf("%lld\n", dfs(0, 0, n));
}
int main(){
init();
solve();
return 0;
}
``````