zoj1500.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <algorithm>
using namespace std;

int	m, len1, len2;
char ord1[50], ord2[50], pos[50];

int c(int a, int b){
    if (a < b) return 0;
    int ret = 1, i;
    if (a - b < b) b = a - b;
    for (ret = i = 1; i <= b; i++) ret = ret * (a - i + 1) / i;
    return ret;
}

int calc(int l, int r){
    int ret = 1;
    int t = 0, last;   
    int ps = pos[ord1[l]] + l - r; 
    for (l++ ; l <= r; l += last, ps += last, t++){
        last = pos[ord1[l]] - ps + 1;
        ret *= calc(l, l + last - 1);
    }
    ret *= c(m, t);
    return ret;
}

void solve(){
    len1 = strlen(ord1); len2 = strlen(ord2);
    for (int i = 0; i < len1; i++) ord1[i] -= 'a';
    for (int i = 0; i < len2; i++) ord2[i] -= 'a', pos[ord2[i]] = i;
    printf("%d\n", calc(0, len1 - 1));
}

int main(){
    while (scanf("%d", &m), m){
        scanf("%s %s", ord1, ord2);
        solve();
    }
}