uva 11027 - Palindromic Permutation（组合数） - c++编程基础

题目大意：给出字符串，以及n，然后字符串中的字母排序可以组成若干的字符串，有些为回文串，输出第n个回文串，若不存在第n个回文串，输出“XXX”。

解题思路：以为n非常大，所以用枚举是由点不太现实的，对于一个字符串，若能重排成回文串，说明每个字母出现的次数都为偶数，或者说为奇数的只有一个（可以放在中间）；然后这样我们就可以将字符缩减一半，构造左半边的字符串（注意若有单个字符输出时要加上）。

接下来就是枚举各个位置上的字符了，例如aaaabb，有4个a， 2个b（处理完的，即原先有8个a，4个b），n为11.

若‘a'放在第一位，还剩3个a和2个b，可以组成（3 + 2）！ / (3!*2!) = 10. 因为10 < 11,所以说第一位不能是’a'， n -= 10，然后n = 1.

现在考虑‘b'放在第一位，还剩4个a和1个b，可以组成（4 + 1)! / (4!*1!)= 5, 因为5 > 1，所以说可以确定第一位是’b'，这是n不用减。

然后一次类推，构造出目标回文串。

#include   
#include   
const int N = 50;  
  
long long tmp[N];  
long long n, c[N];  
  
void init() {  
    tmp[0] = 1;  
    for (long long i = 1; i <= 15; i++)  
        tmp[i] = tmp[i - 1] * i;  
}  
  
long long count(int t) {  
    long long sum = 1;  
    for (int i = 0; i < 26; i++)  
        sum *= tmp[c[i]];  
    return tmp[t] / sum;  
}  
  
void solve() {  
    int cnt = 0, sum = 0, a = 0;  
    char ans[N], ch = '\0';  
    for (int i = 0; i < 26; i++) {  
        if (c[i] % 2) {  
            ch = 'a' + i;  
            cnt++;  
        }  
        sum += c[i] /= 2;  
    }  
  
    if (cnt >




 1 || count(sum) < n) {  
        printf("XXX\n");  
        return ;  
    }  
  
    bool flag = false;  
    while (sum != a) {  
        for (int i = 0; i < 26; i++) {  
  
            if (c[i]) {  
                c[i]--;  
                long long k = count(sum - a - 1);  
                c[i]++;  
                if (n <= k) {  
                    ans[a++] = 'a' + i;  
                    c[i]--;  
                    break;  
                } else {  
                    n -= k;  
                }  
            }  
        }  
    }  
  
    for (int i = 0; i < a; i++)  
        printf("%c", ans[i]);  
    if (ch != '\0') printf("%c", ch);  
    for (int i = a - 1; i >= 0; i--)  
        printf("%c", ans[i]);  
    printf("\n");  
}  
  
int main () {  
    init();  
    int cas, t = 1;  
    char str[N];  
    scanf("%d", &cas);  
    while (cas--) {  
        scanf("%s %lld", str, &n);  
        int len = strlen(str);  
        memset(c, 0, sizeof(c));  
        for (int i = 0; i < len; i++)  
            c[str[i] - 'a']++;  
        printf("Case %d: ", t++);  
        solve();      
    }  
    return 0;  
}